关于微信公众号

Easy

Did it!

#!/usr/bin/env python3

from random import randint
import sys
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def did(n, l, K, A):
	A, K = set(A), set(K)
	R = [pow(_, 2, n) + randint(0, 1) for _ in A - K]
	return R

def main():
	border = "+"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border*72)

	_flag = False
	n, l = 127, 20
	N = set(list(range(0, n)))
	K = [randint(0, n-1) for _ in range(l)]
	cnt, STEP = 0, 2 * n // l - 1
	
	while True:
		ans = sc().decode().strip()
		try:
			_A = [int(_) for _  in ans.split(',')]
			if len(_A) <= l and set(_A).issubset(N):
				DID = did(n, l, K, _A)
				pr(border, f'DID = {DID}')
				if set(_A) == set(K):
					_flag = True
			else:
				die(border, 'Exception! Bye!!')
		except:
			die(border, 'Your input is not valid! Bye!!')
		if _flag:
			die(border, f'Congrats! the flag: {flag}')
		if cnt > STEP:
			die(border, f'Too many tries, bye!')
		cnt += 1

if __name__ == '__main__':
	main()

题目描述起来很简单，即使服务端生成一个有 20 个元素的集合 K，然后你有 11 次机会去猜。你可以输出一个集合 A，服务端会计算集合 $A-K$，并对其中的每一个元素进行计算并返回 ${2^i+j|i\in K-1,j \in (0,1)}$

如果我们有无限次机会，那我们就可以一个一个元素猜，如果返回空集，那么说明我们猜对了。

不过我们只有11次机会，一共有127个元素，因此我们可以一次猜 12 个元素，然后根据返回的集合，我们对这次猜的12个元素，计算 $2^i,2^i+1$，如果它存在于返回的集合中，说明这个元素不在 K 里，舍弃。（不过由于实在模 127 下的计算，不排除有 “误杀” 的情况，因此我们可以一次多输入几个元素，这样能多几次判断。

from pwn import *


# context.log_level = 'debug'
while True:
    sh = remote("00.cr.yp.toc.tf",11337)
    sh.recvuntil("ready?")
    sh.recvuntil("+++\n")
    n=127
    A = [] 
    for l in range(11):
        for _ in range(1):
            reques = ','.join(str( (_ + 15*l)%127) for _ in range(0,20))
            sh.sendline(reques)
            sh.recvuntil("+ DID = ")
            res = sh.recvuntil("\n")[:-1]
            res = eval(res)
        #print(res)
            for tries in [(_ + 15*l)%127 for _ in range(0,20)]:
                if (pow(tries,2,n) not in res) and (pow(tries,2,n)+1 not in res) and tries not in A:
                    A.append(tries)
        print(len(A),A)
        if len(A) == 20:
            reques = ','.join(str(_) for _ in A)
            sh.sendline(reques)
            sh.interactive()
    sh.close()
    
+ DID = []
+ Congrats! the flag: CCTF{W4rM_Up_CrYpt0_Ch4Ll3n9e!!}

Suction

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		e, n = getPrime(16), p * q
		phi = (p - 1) * (q - 1)
		if GCD(e, phi) == 1:
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 128
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

题目就是一个标准的 RSA，p,q 很短只有 128 bit。不过给出的信息中，密文和公钥对的低 8 bit 都被隐藏了。那就进行一个破的爆，

from Crypto.Util.number import *
m = (55208723145458976481271800608918815438075571763947979755496510859604544396672>>8)<<8

for i in range(256):
    for each in sieve_base:
        if (m+i)%each == 0:
            break
    else:
        print(m+i)

55208723145458976481271800608918815438075571763947979755496510859604544396571
55208723145458976481271800608918815438075571763947979755496510859604544396573
55208723145458976481271800608918815438075571763947979755496510859604544396577
55208723145458976481271800608918815438075571763947979755496510859604544396583
55208723145458976481271800608918815438075571763947979755496510859604544396589
55208723145458976481271800608918815438075571763947979755496510859604544396603
55208723145458976481271800608918815438075571763947979755496510859604544396613
55208723145458976481271800608918815438075571763947979755496510859604544396633
55208723145458976481271800608918815438075571763947979755496510859604544396643
55208723145458976481271800608918815438075571763947979755496510859604544396667
55208723145458976481271800608918815438075571763947979755496510859604544396723
55208723145458976481271800608918815438075571763947979755496510859604544396751
55208723145458976481271800608918815438075571763947979755496510859604544396783

然后去factordb查了一下，发现 55208723145458976481271800608918815438075571763947979755496510859604544396613 的两个因子是一样长的，因此就决定是他了。

然后就是直接爆破 e 和 c 尝试进行解密了

p=188473222069998143349386719941755726311
q=292926085409388790329114797826820624883
n=p*q
c=127194641882350916936065994389482700479720132804140137082316257506737630761
phi = (p-1)*(q-1)


for i in range(1,256):
    for j in range(256):
        e = (128<<8)+i
        try:
            tmpc = (c<<8)+j
            d = inverse(e,phi)
            m = int(pow(tmpc,d,n))
            if m<2^200:
                print(long_to_bytes(m))
        except:
            pass

b'6oRYGy&Dc$G2ZS'

Blue_Office

#!/usr/bin/enc python3

import binascii
from secret import seed, flag

def gen_seed(s):
	i, j, k = 0, len(s), 0
	while i < j:
		k = k + ord(s[i])
		i += 1
	i = 0
	while i < j:
		if (i % 2) != 0:
			k = k - (ord(s[i]) * (j - i + 1))            
		else:
			k = k + (ord(s[i]) * (j - i + 1))
	
		k = k % 2147483647
		i += 1

	k = (k * j) % 2147483647
	return k

def reseed(s):
	return s * 214013 + 2531011

def encrypt(s, msg):
	assert s <= 2**32
	c, d = 0, s
	enc, l = b'', len(msg)
	while c < l:
		d = reseed(d)
		enc += (msg[c] ^ ((d >> 16) & 0xff)).to_bytes(1, 'big')
		c += 1
	return enc

enc = encrypt(seed, flag)
print(f'enc = {binascii.hexlify(enc)}')

题目内容也是很简单，有点类似于使用流密码对密文进行一个逐字节的加密，不过这里的区别于 LCG 的地方在于这里没有模数，而且加密使用的密钥为 (d >> 16) & 0xff) ，从低往高第 16-24 比特。

那么注意到 (d >> 16) & 0xff) 其实等价于 $(d \mod {2^{24}})//16$，所以整个运算（包括密钥流的生成）都可以看做是再模 $2^{24}$ 下进行的，又因为我们知道 flag 的格式，开头是一个 ‘C’，于是我们先计算出(d >> 16) & 0xff)，然后再爆破一下低 16 位就可以了。

def reseed(s):
    pass
def encrypt(s, msg):
    pass

enc =  'b0cb631639f8a5ab20ff7385926383f89a71bbc4ed2d57142e05f39d434fce'
enc = bytes.fromhex(enc)
s = ord('C')^0xb0

for e in range(2**16):
	seed = (s<<16)+e
	flag = encrypt(seed,enc[1:])
	if b"CTF" in flag:
		print(f'enc = C{flag.decode()}')
		break

Medium

Derik

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import C, e, d, p, q, r, flag

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]

assert isPrime(e) and isPrime(d) and isPrime(p) and isPrime(q) and isPrime(r)
assert C[0] * p - C[1] * q >= 0
assert C[2] * q - C[3] * r >= 0
assert C[4] * r - C[5] * p >= 0
assert (C[0] * p - C[1] * q) ** e + (C[2] * q - C[3] * r) ** e + (C[4] * r - C[5] * p) ** e == d * (C[0] * p - C[1] * q) * (C[2] * q - C[3] * r) * (C[4] * r - C[5] * p)
assert C[6] * e - C[7] * d == O[3]

n = e * d * p * q * r
m = bytes_to_long(flag)
c = pow(m, 65537, n)
print(f'C = {C}')
print(f'c = {c}')

还是基于 RSA，n 的各个因子被疯狂约束

$(c_0 p -c_1q)^e+(c_2 q -c_3r)^e+(c_4 r -c_5p)^e=d(c_0p-c_1q)(c_2 q -c_3r)(c_4 r -c_5p)$

式子两边要齐次，因此这个 $e$ 应该是 $3$，又因为 $c_6e-c_7d=o_3$，所以这个 $d= 73$，确实是个素数。

于是我们得到式子

(c0*p - c1*q)^3 + (c2*q - c3*r)^3 + (c4*p - c5*r)^3  == 73*(c0*p - c1*q)*(c2*q - c3*r)*(c4*p - c5*r)

好像并没有什么头绪，这个时候我们注意到列表 O 里面的数字好像都没有用到，于是尝试一下

assert O[0]^3+O[1]^3+O[2]^3 == 73 * O[0]* O[1]* O[2]

（对上出题人脑电波了）发现能通过，于是我们就有新的约束了

from Crypto.Util.number import *
#from secret import C, e, d, p, q, r, flag

O = [1391526622949983, 2848691279889518, 89200900157319, 31337]
C = [5960650533801939766973431801711817334521794480800845853788489396583576739362531091881299990317357532712965991685855356736023156123272639095501827949743772, 6521307334196962312588683933194431457121496634106944587943458360009084052009954473233805656430247044180398241991916007097053259167347016989949709567530079, 1974144590530162761749719653512492399674271448426179161347522113979158665904709425021321314572814344781742306475435350045259668002944094011342611452228289, 2613994669316609213059728351496129310385706729636898358367479603483933513667486946164472738443484347294444234222189837370548518512002145671578950835894451, 8127380985210701021743355783483366664759506587061015828343032669060653534242331741280215982865084745259496501567264419306697788067646135512747952351628613, 5610271406291656026350079703507496574797593266125358942992954619413518379131260031910808827754539354830563482514244310277292686031300804846114623378588204, 10543, 4]
c = 80607532565510116966388633842290576008441185412513199071132245517888982730482694498575603226192340250444218146275844981580541820190393565327655055810841864715587561905777565790204415381897361016717820490400344469662479972681922265843907711283466105388820804099348169127917445858990935539611525002789966360469324052731259957798534960845391898385316664884009395500706952606508518095360995300436595374193777531503846662413864377535617876584843281151030183895735511854

e = 3
d = (C[6] * e - O[3]) // C[7]

var('p,q,r')
f1 = C[0] * p - C[1] * q - O[0]
f2 = C[2] * q - C[3] * r - O[1]
f3 = C[4] * r - C[5] * p - O[2]

m = solve([f1,f2,f3],p,q,r)
p = m[0][0].rhs()
q = m[0][1].rhs()
r = m[0][2].rhs()

phi = (p-1)*(q-1)*(r-1)*(e-1)*(d-1)
m = pow(c,inverse(65537,int(phi)),p*q*r*e*d)
print(long_to_bytes(int(m)))

barak

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def on_barak(P, E):
	c, d, p = E
	x, y = P
	return (x**3 + y**3 + c - d*x*y) % p == 0

def add_barak(P, Q, E):
	if P == (0, 0):
		return Q
	if Q == (0, 0):
		return P
	assert on_barak(P, E) and on_barak(Q, E)
	x1, y1 = P
	x2, y2 = Q
	if P == Q:
		x3 = y1 * (c - x1**3) * inverse(x1**3 - y1**3, p) % p
		y3 = x1 * (y1**3 - c) * inverse(x1**3 - y1**3, p) % p
	else:

		x3 = (y1**2*x2 - y2**2*x1) * inverse(x2*y2 - x1*y1, p) % p
		y3 = (x1**2*y2 - x2**2*y1) * inverse(x2*y2 - x1*y1, p) % p
	return (x3, y3)

def mul_barak(m, P, E):
	if P == (0, 0):
		return P
	R = (0, 0)
	while m != 0:
		if m & 1:
			R = add_barak(R, P, E)
		m = m >> 1
		if m != 0:
			P = add_barak(P, P, E)
	return R

def rand_barak(E):
	c, d, p = E
	while True:
		y = randint(1, p - 1)
		K = Zmod(p)
		P.<x> = PolynomialRing(K) 
		f = x**3 - d*x*y + c + y^3
		R = f.roots()
		try:
			r = R[0][0]
			return (r, y)
		except:
			continue

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
c = 1
E = (c, d, p)

P = rand_barak(E)

FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
m = bytes_to_long(FLAG) 
assert m < p
Q = mul_barak(m, P, E)
print(f'P = {P}')
print(f'Q = {Q}')

题目构造的曲线为 $y^3 \equiv -x^3+dxy-c \pmod p$

然后给出曲线参数和曲线上的两个点 $P,Q=mP$，其中 $m$ 为 flag，因此是一个在该曲线上的 DLP。

以往这种题一般是想办法找到同态，但是我脑子不好，遇到这种题一般都想不出来。但是从春哥那学到了一种能调sagemath包的新姿势

首先想办法把式子构造成其次且具有三个变量的三次多项式，于是这里我们增加一个变量 $z$，将式子变为
$$
y^3 \equiv -x^3+dxyz-cz^3 \pmod p
$$
当 $z=1$ 的时候就是我们原来的曲线

然后我们调一手 EllipticCurve_from_cubic，然后就可以调 DLP 了。

p = 73997272456239171124655017039956026551127725934222347
d = 68212800478915688445169020404812347140341674954375635
R.<x,y,z> = Zmod(p)[]
cubic = x^3+y^3-d*x*y*z+z^3
P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714,1)
E = EllipticCurve_from_cubic(cubic, P, morphism=True)

P = (71451574057642615329217496196104648829170714086074852, 69505051165402823276701818777271117086632959198597714,1)
Q = (40867727924496334272422180051448163594354522440089644, 56052452825146620306694006054673427761687498088402245,1)

PP = E(P)
QQ = E(Q)

m = QQ.discrete_log(PP)

# 1780694557271320552511299360138314441283923223949197

但这里还并不是flag，我们得到的应该是 flag % P.order，所以还需要枚举一下。

m = 1780694557271320552511299360138314441283923223949197
o = int(P.order())
while True:
    m+=o
    if all( 30<x<125 for x in long_to_bytes(int(m))):
        print(long_to_bytes(int(m)))
        break

# '_hE5S!4n_f0rM_0F_3CC!!

EllipticCurve_from_cubic(F, P=None, morphism=True)

在标准射影坐标系中，Weierstrass 形式的椭圆曲线方程可以表示为 $Y^2Z=X^3+aXZ^2+Z^3$，注意到这就是一个 cubic，我们使用 EllipticCurve_from_cubic 就是将一个射影坐标系中的一条曲线态射（morphism）到仿射坐标系中的一条曲线。如果设置 morphism=True，则会返回态射函数，如果设置 morphism=False，则仅仅返回曲线，也可以直接使用函数 Jacobian(F) 代替。

在上述例子中，我们的态射 E 为

sage: E
Scheme morphism:
  From: Projective Plane Curve over Ring of integers modulo 73997272456239171124655017039956026551127725934222347 defined by x^3 + y^3 + 5784471977323482679485996635143679410786050979846712*x*y*z + z^3
  To:   Elliptic Curve defined by y^2 + 41848246294228984089267712788268151466593112763848031*x*y = x^3 + 8186198475255690096811875068967290988967924587416530*x^2 + 67041837351181533250843830910913901867849396421579685*x + 40673641660869730385035838198800394713965979400200155 over Ring of integers modulo 73997272456239171124655017039956026551127725934222347
  Defn: Defined on coordinates by sending (x : y : z) to
        (9167218108590654299487009181696317855454416112239889*y + 3279765642505352830157211697766991850038465138705271*z : 5784471977323482679485996635143679410786050979846712*y : 64249990329941531194735759683164021211133831031453155*x + 22688267644108754864364901498104863155005679028019334*y + 42580013058247064141816874924090310799821854717107287*z)

我们可以取 P 的参数进行验证

# 取 P 点 三个坐标 x,y,z
sage: x=P[0]
sage: y=P[1]
sage: z=P[2]
# 根据态射计算值，可以得到射影坐标(X:Y:Z),转化为仿射坐标(X/Z:Y/Z)
sage: (9167218108590654299487009181696317855454416112239889*y + 3279765642505352
....: 830157211697766991850038465138705271*z)/(642499903299415311947357596831640
....: 21211133831031453155*x + 2268826764410875486436490149810486315500567902801
....: 9334*y + 42580013058247064141816874924090310799821854717107287*z)%p
67918738637341461863982616331391010431949134469044189
sage: E(P)[0]
67918738637341461863982616331391010431949134469044189

这一部分难度的题大多都有现成的板子，不过死用板子可不行，还需要有一定的理解，得变着法儿来用板子。

RISK

#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import m, flag

def genPrime(m, nbit):
	assert m >= 2
	while True:
		a = getRandomNBitInteger(nbit // m)
		r = getRandomNBitInteger(m ** 2 - m + 2)
		p = a ** m + r
		if isPrime(p):
			return (p, r)

def genkey(m, nbit):
	p, r = genPrime(m, nbit // 2)
	q, s = genPrime(m, nbit // 2)
	n = p * q
	e = r * s
	return (e, n)

def encrypt(msg, pkey):
	e, n = pkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

pkey = genkey(m, 2048)
enc = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

仍然是 RSA 公钥密码系统， $n = (a^4+r)(b^4+s)=(ab)^4+sa^4+rb^4+rs$，其中 $e=rs$ 已知。于是我们可以计算 $\lfloor \sqrt[4]{n}\rfloor=ab$，因此有 $c = n-(ab)^4-rs = sa^4+rb^4$

总共四个未知数，我们已知 $ab,rs$ 和 $c$。理论上是解不出来的，不过由于 $rs$ 并不大，我们可以爆破他的因子来恢复 $r,s$，从而计算得到 $a,b$，同时也能恢复 $p,q$

from gmpy2 import *
from sympy import isprime
n=373824666550208932851344358703053061405262438259996622188837935528607451817812480600479188884096072016823491996056842120586016323642383543231913508464973502962030059403443181467594283936168384790367731793997013711256520780338341018619858240958105689126133812557401122953030695509876185592917323138313818881164334490044163316692588337720342646339764174333821950301279825316497898035760524780198230860089280791887363472060435443944632303774987556026740232641561706904946900169858650106994947597642013168757868017723456208796677559254390940651802333382820063200360490892131573853635471525711894510477078934343423255983

ab = int(iroot(n,4)[0])
ab4 = ab^4

rs = 150953688
for r in rs.divisors():
    s = rs//r
    c = n-ab4-rs
    delta = c^2-4*rs*ab4
    sdelta = int(iroot(delta,2)[0])
    a4 = (c+sdelta)//(2*s)
    if iroot(a4,4)[1]:
        a = int(iroot(a4,4)[0])
        b = int(iroot(ab4,4)[0]//a)
        if isprime(a^4+r):
            print("[+] p=",a^4+r)
            print("[+] q=",n//(a^4+r))
        elif isprime(a^4+s):
            print("[+] p=",a^4+s)
            print("[+] q=",n//(a^4+s))
            
[+] p= 24854995563762799317055160315647073592768859410925406616067526817964296709994775588158311030813096922905657553370793515214591086698010302872311633588541111630338981703494212247996116660819640489213219705595382514374022123356637290058228183400682431815794876393612877273757515867990847040787313812864434536969
[+] q= 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807

之后就是解一个 RSA，不过

sage: gcd(rs,p-1)
mpz(10728)
sage: gcd(rs,q-1)
mpz(6)

这就比较麻烦，需要在域下开个根。掏出 AMM 板子

import random
import time
from tqdm import tqdm
from Crypto.Util.number import *
# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def onemod(p,r): 
    t=random.randint(2,p)
    while pow(t,(p-1)//r,p)==1: 
         t=random.randint(2,p)
    return pow(t,(p-1)//r,p) 
 
def solution(p,root,e):  
    while True:
        g=onemod(p,e) 
        may=[] 
        for i in tqdm(range(e)): 
            may.append(root*pow(g,i,p)%p)
        if len(may) == len(set(may)):
            return may


def solve_in_subset(ep,p):
    cp = int(pow(c,inverse(int(e//ep),p-1),p))
    com_factors = []
    while GCD(ep,p-1) !=1:
        com_factors.append(GCD(ep,p-1))
        ep //= GCD(ep,p-1)
    com_factors.sort()

    cps = [cp]
    for factor in com_factors:
        mps = []
        for cp in cps:
            mp = AMM(cp, factor, p)
            mps += solution(p,mp,factor)
        cps = mps
    for each in cps:
        assert pow(each,e,p)==c%p
    return cps




p = 24854995563762799317055160315647073592768859410925406616067526817964296709994775588158311030813096922905657553370793515214591086698010302872311633588541111630338981703494212247996116660819640489213219705595382514374022123356637290058228183400682431815794876393612877273757515867990847040787313812864434536969
q = 15040222622096320078383580808680733765955114958694997949647342925417877088612792495485641348591026281373930569798925789027166056695954731923306109646611840570310396750856642056018981080439916663195842593441587057719678555907050674529272376248049062724657792390788687452049496308886252188791975094655675938807
e = 150953688
c = 275574424285842306309073814038154403551700455145115884031072340378743712325975683329051874910297915882286569143815715537085387363420246497061870251520240399514896001311724695996978111559476733709139080970977190150345474341853495386364275702356438666152069791355990718058189043717952080875207858163490627801836274404446661613239167700736337269924479349700031535265765885064606399858172168036794462235707003475360358004643720927563261787867952228496769300443415094124132722170498229611285689671203272698693505808912907778910378274197503048226322090611405601517624884408718689404556983397217070272851442351897456769883

ep = 10728
eq = 72
m_p = solve_in_subset(ep,p)
m_q = solve_in_subset(eq,q)

start = time.time()
print('Start CRT...')
for mpp in m_p:
    for mqq in m_q:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if solution < 2^800 :   # Always the bit_length of flag is less than 800
            print(long_to_bytes(solution))


end = time.time()
print("Finished in {} seconds.".format(end - start))

# CCTF{S!mP1E_A7t4cK_0n_SpEc1aL-5trucTur3D_RSA_pR1me5!}

Roldy

#!/usr/bin/env python3

from Crypto.Util.number import *
from pyope.ope import OPE as enc
from pyope.ope import ValueRange
import sys
from secret import key, flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc(): 
	return sys.stdin.buffer.readline()

def encrypt(msg, key, params):
	if len(msg) % 16 != 0:
		msg += (16 - len(msg) % 16) * b'*'
	p, k1, k2 = params
	msg = [msg[_*16:_*16 + 16] for _ in range(len(msg) // 16)]
	m = [bytes_to_long(_) for _ in msg]
	inra = ValueRange(0, 2**128)
	oura = ValueRange(k1 + 1, k2 * p + 1)
	_enc = enc(key, in_range = inra, out_range = oura)
	C = [_enc.encrypt(_) for _ in m]
	return C

def main():
	border = "|"
	pr(border*72)
	pr(border, " Welcome to Roldy combat, we implemented an encryption method to    ", border)
	pr(border, " protect our secret. Please note that there is a flaw in our method ", border)
	pr(border, " Can you examine it and get the flag?                               ", border)
	pr(border*72)

	pr(border, 'Generating parameters, please wait...')
	p, k1, k2 = [getPrime(129)] + [getPrime(64) for _ in '__']
	C = encrypt(flag, key, (p, k1, k2))

	while True:
			pr("| Options: \n|\t[E]ncrypted flag! \n|\t[T]ry encryption \n|\t[Q]uit")
			ans = sc().decode().lower().strip()
			if ans == 'e':
				pr(border, f'encrypt(flag, key, params) = {C}')
			elif ans == 't':
				pr(border, 'Please send your message to encrypt: ')
				msg = sc().rstrip(b'\n')
				if len(msg) > 64:
					pr(border, 'Your message is too long! Sorry!!')
				C = encrypt(msg, key, (p, k1, k2))
				pr(border, f'C = {C}')
			elif ans == 'q':
				die(border, "Quitting ...")
			else:
				die(border, "Bye ...")

if __name__ == '__main__':
	main()

交互题，

选项 e 可以提供一个 flag 的密文

选项 t 可以加密用户的输入（短于64字节）并返回密文。

我们看到加密，

def encrypt(msg, key, params):
	if len(msg) % 16 != 0:
		msg += (16 - len(msg) % 16) * b'*'
	p, k1, k2 = params
	msg = [msg[_*16:_*16 + 16] for _ in range(len(msg) // 16)]
	m = [bytes_to_long(_) for _ in msg]
	inra = ValueRange(0, 2**128)
	oura = ValueRange(k1 + 1, k2 * p + 1)
	_enc = enc(key, in_range = inra, out_range = oura)
	C = [_enc.encrypt(_) for _ in m]
	return C

是一个分组加密，将明文以 16 字节进行分组，不足的用 * 补齐，然后调用一种叫做 OPE 的加密算法进行加密，其中 key, k1, k2, p 均未知， k1，k2，p 和 out_range 相关，out_range = (k1 + 1, k2 * p + 1)

那么我们来简单看一下这个 OPE，直接去pypi看，其中提到 This is an implementation of Boldyreva symmetric order-preserving encryption scheme (Boldyreva’s paper). 这是一种保序加密的实现，那么何为”保序“呢？下面给出了例子

from pyope.ope import OPE
cipher = OPE(b'key goes here')
assert cipher.encrypt(1000) < cipher.encrypt(2000) < cipher.encrypt(3000)
assert cipher.decrypt(cipher.encrypt(1337)) == 1337

那么解题思路就清晰了（甚至没有看具体的加密算法）

1. 首先获取 flag 的密文 enc(flag)

2. 设置一个下限 floor，设置一个上限 sky，设置一个 mid = (floor+sky)//2

3. 获取 enc(mid)

4. 如果 enc(mid) > enc(flag)，则 sky = mid

5. 如果 enc(mid) < enc(flag)，则 floor = mid

6. 如果 enc(mid) = enc(flag)，则 flag = mid，完成解题；否则重复步骤 3 - 6。

   （远程服务好像有问题，虽然是 While True，但是一般6-8次交互后就会强制断掉，好在 flag 是不变的，我们可以重复连接）

from pwn import *
from Crypto.Util.number import *

context.log_level = 'debug'
sh = remote("06.cr.yp.toc.tf",31377)
sh.recvuntil("[Q]uit\n")
sh.sendline("E")
sh.recvuntil("params) = ")
flag_enc = eval(sh.recvuntil("]"))

floor1 = 0
sky1 = (2**128)-1
floor2 = 0
sky2 = (2**128)-1
floor3 = 0
sky3 = (2**128)-1
floor4 = 0
sky4 = (2**128)-1


for _ in range(168):
	try:
		mid1 = (floor1+sky1)//2
		mid2 = (floor2+sky2)//2
		mid3 = (floor3+sky3)//2
		mid4 = (floor4+sky4)//2
		sh.recvuntil("[Q]uit\n")
		sh.sendline("T")
		data = long_to_bytes(mid1)+long_to_bytes(mid2)+long_to_bytes(mid3)+long_to_bytes(mid4)
		sh.sendline(data)
		sh.recvuntil("C = ")
		data_enc = eval(sh.recvuntil("]"))
		if data_enc[0] > flag_enc[0]:
			sky1 = mid1
		elif data_enc[0] < flag_enc[0]:
			floor1 = mid1
		else:
			print("[+] ",long_to_bytes(mid1))

		if data_enc[1] > flag_enc[1]:
			sky2 = mid2
		elif data_enc[1] < flag_enc[1]:
			floor2 = mid2
		else:
			print("[+] ",long_to_bytes(mid2))

		if data_enc[2] > flag_enc[2]:
			sky3 = mid3
		elif data_enc[2] < flag_enc[2]:
			floor3 = mid3
		else:
			print("[+] ",long_to_bytes(mid3))

		if data_enc[3] > flag_enc[3]:
			sky4 = mid4
		elif data_enc[3] < flag_enc[3]:
			floor4 = mid4
		else:
			print("[+] ",long_to_bytes(mid4))

		print(_,mid1,mid2,mid3,mid4)
	except:
		sh.close()
		sh = remote("06.cr.yp.toc.tf",31377)
		sh.recvuntil("[Q]uit\n")
		sh.sendline("E")
		sh.recvuntil("params) = ")
		flag_enc = eval(sh.recvuntil("]"))

[DEBUG] Sent 0x2 bytes:
    b'T\n'
[DEBUG] Sent 0x41 bytes:
    b'CCTF{Boldyreva_5ymMe7rIC_0rD3r_pRe5Erv!n9_3nCryp7i0n!_LStfig9TM}\n'
[DEBUG] Received 0x28 bytes:
    b'| Please send your message to encrypt: \n'
[DEBUG] Received 0x135 bytes:
    b'| C = [2599038725030407463903804797382365452856395373775921222259, 4691931002839804444939519387512017276102085486050513350917, 3183751470526374746059757707916120807018893056051312221576, 2141073881141548858839412849804595194017377913807338508876]\n'
    b'| Options: \n'
    b'|\t[E]ncrypted flag! \n'
    b'|\t[T]ry encryption \n'
    b'|\t[Q]uit\n'
[+]  b'CCTF{Boldyreva_5'
[+]  b'ymMe7rIC_0rD3r_p'
[+]  b'Re5Erv!n9_3nCryp'
[+]  b'7i0n!_LStfig9TM}'

Insights

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def getRandomNBits(n):
	nb = '1' + ''.join([str(randint(0, 1)) for _ in range(n - 1)])
	return nb

def getLeader(L, n):
	nb = L + getRandomNBits(n)
	return int(nb, 2)

def genPrime(L, nbit):
	l = len(L)
	assert nbit >= l
	while True:
		p = getLeader(L, nbit - l)
		if is_prime(p):
			return p

def genKey(L, nbit):
	p, q = [genPrime(L, nbit) for _ in '__']
	n = p * q
	d = next_prime(pow(n, 0.2919))
	phi = (p - 1) * (q - 1)
	e = inverse(d, phi)
	pubkey, privkey = (n, e), (p, q)
	return pubkey, privkey

def encrypt(msg, pubkey):
	n, e = pubkey
	m = bytes_to_long(msg)
	c = pow(m, e, n)
	return c

nbit = 1024
L = bin(bytes_to_long(b'Practical'))[2:]
pubkey, privkey = genKey(L, nbit)
p, q = privkey
c = encrypt(flag, pubkey)

print('Information:')
print('-' * 85)
print(f'n = {p * q}')
print(f'e = {pubkey[1]}')
print(f'c = {c}')
print(f'p = {bin(p)[2:len(L)]}...[REDACTED]')
print(f'q = {bin(q)[2:len(L)]}...[REDACTED]')
print('-' * 85)

虽然代码很长，但总结下来，就是一个基础的 RSA 加密体制，但是 $d \lt n^{0.291}$，另外给出了 71 比特的 p,q 高位，并且这部分比特是相等的。

熟悉 RSA 低私钥攻击的读者肯定知道 Boneh-Durfee 攻击，而其理论界是 0.292。虽然这里的界似乎确实是小于 0.292，但正如题目中所指出的 Practical，想要达到这个理论界几乎是不可能的。于是我们需要从额外给出 p,q 高 72 比特入手。

回顾一下 Boneh-Durfee 攻击，我们设 $d = n^{i},e=n^{\alpha}$

根据公钥和私钥的关系，我们有

$ed = 1+\frac{k\varphi(n)}{2} $，

其中 $\varphi(n)=(p-1)(q-1)=n-p-q+1$，

因此可以写为 $ed = 1+k(\frac{n+1}{2}-\frac{p+q}{2})$，

记 $x = \frac{n+1}{2},y=-\frac{p+q}{2}$，

于是式子简化为 $1=ed+k(x+y)$

我们将式子放在模 $e$ 的剩余系下，得到同余式
$$
k(x+y)\equiv 1 \pmod e
$$
由于 $y = O(\sqrt N),k \lt \frac{2ed}{\varphi(n)}\le\frac{3ed}{n}\lt3n^{\alpha+i-1}$，

因此我们使用 coppersmith 对二元同余式 $f(x,y)\equiv k(x+y) \equiv 1 \pmod e$ 求小根能够得到 $k,y$，从而分解 $n$。

那么对于本题，我们应该利用额外的信息来减小需要求的 $k,y$

我们设 $p = \bar p+p’,q = \bar q + q$，于是
$$
x+y=\frac{n+1}{2}-\frac{p+q}{2}=\frac{n+1}{2}-\frac{\bar p + p’+\bar q+q’}{2}=\frac{n+1-\bar p - \bar q}{2}-\frac{p’+q’}{2}
$$
这样我们需要的 $y=\frac{p’+q’}{2}$ 就要小很多了。

然后我们掏出 Boneh-Durfee 板子

'''
# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage
'''
def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 12765231982257032754070342601068819788671760506321816381988340379929052646067454855779362773785313297204165444163623633335057895252608396010414744222572161530653104640020689896882490979790275711854268113058363186249545193245142912930804650114934761299016468156185416083682476142929968501395899099376750415294540156026131156551291971922076435528869024742993840057342092865203064721826362149723366381892539617642364692012936270150691803063945919154346756726869466855557344213050973081755499746750276623648407677639812809665472258655462846021403503851719008687214848550916999977775070011121527941755954255781343103086789
    # the public exponent
    e = 459650454686946706615371845737527916539205656667844780634386049268800615782964920944229084502752167395446158290854047696006034750210758341744841762479191173017773034647739346927390580848998121830029134542880713409306092967282675122699586503684943407535067216738556403169403622104762516293879994387324370835718056251706150557820106296417750402984941838652433642298378976899556042987560946508887315484380807248331504458640857234708123277403252632993828101306072382329879857946191508782246793011691530554606521701055094223574951862129713872918021549814674387049788995785872980320871421550616327471735316980754238323013

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = .291 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 6 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
    X = 2*floor(N^delta)  # this _might_ be too much
    Y = floor(N^(953/2048))    # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    pbar = int('10100000111001001100001011000110111010001101001011000110110000101101100',2)<<(1024-71)
    A = int((N+1-2*pbar)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
        print("=== checking values ===")
        print("* delta:", delta)
        print("* delta < 0.292", delta < 0.292)
        print("* size of e:", int(log(e)/log(2)))
        print("* size of N:", int(log(N)/log(2)))
        print("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
        print("=== running algorithm ===")
        start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
        print("=== solution found ===")
        if False:
            print("x:", solx)
            print("y:", soly)

        d = int(pol(solx, soly) / e)
        print("private key found:", d)
        c = 10992248752412909788626396175372747713079469256270100576886987393986576680666320383209810005318254336440105142571546847427454822405793626080251363454531982746373841267986148332456716023293306870382809568309620264499225135226626560298741596462262513921032733814032790312163314776421380481083058518893602887082464123177575742160690315666730642727773288362853901330620841098230284739614618790097180848133698381487679399364400048499041582830157094876815030301231505774900176910650887780842536610942820066913075027528705150102760422836458745949063992228680293226303245265232017738712226154128654682937687199768621565945171
        m = pow(c,d,N)

        print("message found:", long_to_bytes(int(m)))
    else:
        print("=== no solution was found ===")

    if debug:
        print("=== %s seconds ===" % (time.time() - start_time))

if __name__ == "__main__":
    example()
    
=== solution found ===
private key found: 693984516363754919249700902493753051718166208912377865278483876234349619419200560616162942304659132290614866566556420934365717915837808485622613368180482591406570741380374249603517
message found: b'CCTF{RSA_N3w_rEc0rd5_4Nd_nEw_!nSi9h75!}'
=== 11.820068597793579 seconds ===

非预期

令人意想不到的出题失误，注意到 $d$ 的生成方式 d = next_prime(pow(n, 0.2919))，使用的函数是 next_prime，因此这个私钥我们可以直接计算出来。（emmm，难崩）

Resuction

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

from decimal import *

def keygen(nbit, r):
	while True:
		p, q = [getPrime(nbit) for _ in '__']
		d, n = getPrime(64), p * q
		phi = (p - 1) * (q - 1)
		if GCD(d, phi) == 1:
			e = inverse(d, phi)
			N = bin(n)[2:-r]
			E = bin(e)[2:-r]
			PKEY = N + E
			pkey = (n, e)
			return PKEY, pkey

def encrypt(msg, pkey, r):
	m = bytes_to_long(msg)
	n, e = pkey
	c = pow(m, e, n)
	C = bin(c)[2:-r]
	return C

r, nbit = 8, 1024
PKEY, pkey = keygen(nbit, r)
print(f'PKEY = {int(PKEY, 2)}')
FLAG = flag.lstrip(b'CCTF{').rstrip(b'}')
enc = encrypt(FLAG, pkey, r)
print(f'enc = {int(enc, 2)}')

如题，是 Suction 一题的升级版，同样的将 $n,e,c$ 的第 8 比特给抛掉了，但这一次的模数比较长，切入点在于私钥 d=getPrime(64) 比较短。使用维纳攻击就可以恢复。于是同 suction一样，我们先排除一些 $n$：爆破 $n$，然后将有小因子的 $n$ 剔除。

from Crypto.Util.number import *
n = (112427415074496733728692221822236708267020071361134595480944452567332776053338591808303191116824668207575885357243149596990683319683952721613109860104563666843168030575222891621946617002107610348479917006441273131192536638336531098426557725336808479141871883466571954197021295145182566118601456967383373633195241318527152234920928439522439998675385534769566753824107447367198956368408576813105163823071250689597585130857134935943413570763481702219998410358821249192007224259883929235667449109565875403158782316445806131091179344390038436184567391800053904246077478412520806972604858022406108303505402566299783227719)<<8

candidate_n=[]
for i in range(256):
    for each in sieve_base:
        if (n+i)%each == 0:
            break
    else:
        candidate_n.append(n+i)
        
print(len(candidate_n))	#18

我们得到 18 个候选 $n$，然后爆破 $e$，掏出维纳攻击板子恢复 $d$

# https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works

cbar = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

ebar = 74815283003042416338002870607297643274871034448602599708384141071471917607169366460779106981614337875374527128073342874020038409390009797167164979588156632069225354809941878042041409035570766771978869694205473027422664974736500767764276542632434961655827607595857636591200768423760020441355451161200288584365600631284260544071893780843946670256375597950133179820952349509047750482890979996176201687343781812761180017866837666545025976113041894068276225989698747704895120678129952143858563031610250246566072046781376525603542675861354076677536820335237963848876218689030737874987393642014514707143849847745550092834

for n in candidate_n:
    for i in range(1,256,2):
        e = (ebar << 8) + i
        d = wiener(e,n)
        if d:
            for j in range(256):
                c = (cbar<<8)+j
                m = int(pow(c,d,n))
                if m.bit_length()<800:
                    print(long_to_bytes(int(pow(c,d,n))).decode())

                    # aIr_pr3s5urE_d!Ff3rEn7i4L_8eTw3eN_ArEa5!

Blobfish

#!/usr/bin/env python3

import os
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from PIL import Image
from PIL import ImageDraw
from flag import flag

key = get_random_bytes(8) * 2
iv = md5(key).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

img = Image.new('RGB', (800, 50))
drw = ImageDraw.Draw(img)
drw.text((20, 20), enc.hex(), fill=(255, 0, 0))
img.save("flag.png")

hkey = ''.join('\\x{:02x}'.format(x) for x in key[:10])

os.system(f'/bin/zip -0 flag.zip flag.png -e -P \"$(/bin/echo -en \"{hkey}\")\"')

分析一下代码，题目使用 8个随机字节 * 2 作为 AES-CFB 的加密密钥加密的 flag，随后将密文作图，并加密打包，压缩包的密码是 AES 密钥的前十个字节。不过看一下 zip 命令，会发现 -0 参数是仅储存。而里面的密文作为图片文件，我们是知道其文件头的，于是我们可以对其实施明文攻击，恢复密钥，获得密文，进而解密密文获得 flag。使用的工具是 github 开源的 bkcrack （何尝不是一个板子）

┌──(kali㉿kali)-[~/Desktop/bkcrack-master/install]
└─$ ./bkcrack -C flag.zip -c flag.png -p plain.png
bkcrack 1.5.0 - 2023-07-12
[03:35:31] Z reduction using 9 bytes of known plaintext
100.0 % (9 / 9)
[03:35:31] Attack on 697990 Z values at index 6
Keys: 03492be6 b81a5123 24d7b146
13.0 % (90955 / 697990)
[03:39:01] Keys
03492be6 b81a5123 24d7b146
                                                                                                                                                            
┌──(kali㉿kali)-[~/Desktop/bkcrack-master/install]
└─$ ./bkcrack -C flag.zip -c flag.png -k 03492be6 b81a5123 24d7b146 -d flag.png
bkcrack 1.5.0 - 2023-07-12
[04:03:00] Writing deciphered data flag.png (maybe compressed)
Wrote deciphered data.
                                                                                                                                                            
┌──(kali㉿kali)-[~/Desktop/bkcrack-master/install]
└─$ ./bkcrack -k 03492be6 b81a5123 24d7b146 --bruteforce ?b --length 10

bkcrack 1.5.0 - 2023-07-12
[04:03:32] Recovering password
length 10...
Password: �n�y*�Z��n (as bytes: ad 6e fb 79 2a ea 5a aa ad 6e)
Some characters are not in the expected charset. Continuing.
100.0 % (65536 / 65536)
[04:03:35] Could not recover password

解密压缩包得到图片

编写解密代码解密密文获得 flag

import os
from hashlib import md5
from Crypto.Cipher import AES

key = b"\xad\x6e\xfb\x79\x2a\xea\x5a\xaa" * 2
iv = md5(key).digest()

enc = bytes.fromhex("69f421d9e241933cbc62a9ffe937779c864ffa193de014aeb57046b16c40c7353910c61a2676f14f4c7737f038a6db53262c50")
cipher = AES.new(key, AES.MODE_CFB, iv=iv)
flag = cipher.decrypt(enc)

print(flag)
# b'CCTF{d3ep-Zip_fi5h_0f_tH3_knOwN_pL4!n_7exT_ATtAcK!}'

ASIv1

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def base(n, l):
    D = []
    while n > 0:
        n, r = divmod(n, l)
        D.append(r)
    return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
	l = len(seed)
	_seed = base(bytes_to_long(seed), 3)
	_seed = [int(_) for _ in _seed]
	_l = len(_seed)
	R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
	S = []
	for r in R:
		s = 0
		for _ in range(_l):
			s += (r[_] * _seed[_]) % 3
		# s += getRandomRange(0, 3)
		s %= 3
		S.append(s)
	return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

题目首先将 flag 转为三进制，随后作为 seed 数组，然后根据 _seed 数组的长度随机生成了一系列随机数组 R，然后对每一个 R 数组做运算
$$
s \equiv \sum{i=0}^{n}r_i \cdot seed_i \pmod 3
$$
题目给出了 R 数组和由 s 组成的 S 数组，所以其实就是在模 3 下解一个线性同余方程组。

from Crypto.Util.number import *

with open("output.txt ") as f:
	data = f.read().split("\n")

R = eval(data[0][4:])
S = eval(data[1][4:])
RR = matrix(Zmod(3),R[:200])
SS = vector(Zmod(3),S[:200])
mm = RR.solve_right(SS)

flag = ''.join(str(i) for i in mm)
flag = int(flag,3)
print(long_to_bytes(flag))

# b'3Xpl0i7eD_bY_AtT4ck3r!'

TPSD

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Welcome, esteemed cryptographers with expertise in number theory!    +
+ It's a pleasure to have you here. Whether you're a seasoned veteran  +
+ or a budding enthusiast, let's dive in and explore the fascinating   +
+ world of cryptography and number theory together!                    +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ We are looking for the integer solution of p^3 + q^3 + r^3 = 1, such +
+ that at least one of p, q, or r is prime. Submit each such triple    +
+ at every step with mentioned properties.                             +
+ Send a triple array of integers whose absolute minimum value has     +
+ almost (6, 26)-bits. You are at level 1:

丢番图方程，需要给出值 $p,q,r$ 满足 $p^3 + q^3 + r^3 =1$，其中满足 $min(|p|,|q|,|e|)\in [2^l,2^h ]$。是一道数学题，也有现成结论，见《On the Diophantine Equation x3+y3+z3= 1》

import random 

t = random.randint(2**6,2**26)
p = 9*t**4
q = -9*t**4+3*t
r = -9*t**3+1

assert p**3+q**3+r**3==1

显然三个参数里面 $r$ 应该是最小的，所以它的满足 $r \in [2^l,2^h]$，其次也只有 $r$ 有可能是一个素数，于是我们在区间内找到一个素数 $r$ 就能通过关卡了。

import random 
from pwn import *
from Crypto.Util.number import *
from sympy import *
context.log_level = 'debug'

sh = remote("05.cr.yp.toc.tf","11137")
while True:
	sh.recvuntil("+ almost (")
	l = int(sh.recvuntil(", ")[:-2])
	h = int(sh.recvuntil(")")[:-1])
	while True:
		t = random.randint(2**(l//3),2**(h//3))
		r = -9*t**3+1
		if isprime(abs(r)) and (2**l)<abs(r)<(2**h):

			break
	p = 9*t**4
	q = -9*t**4+3*t
	sh.recvuntil("level")
	sh.recvuntil(": \n")
	sh.sendline(','.join(str(i) for i in [p,q,r]))


b'+ gj, try the next level :)\n'
    b'+ Send a triple array of integers whose absolute minimum value has     +\n'
    b'+ almost (186, 206)-bits. You are at level 19: \n'
[DEBUG] Sent 0xe7 bytes:
    b'2610575330510601411661135837391203680216386303602680076369749905572234291076173824,-2610575330510601411661135837391203680216386303602680076369749514060588681431841560,-20003813626888652657280145082395768211458812516684950505205247\n'
[DEBUG] Received 0x3f bytes:
    b'+ Congrats! the flag: CCTF{pr1m3S_in_7ErnArY_Cu8!c_3qu4tI0nS!}\n'

Trex

#!/usr/bin/env python3

import random
import sys
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def check_inputs(a, b, c):
	if not all(isinstance(x, int) for x in [a, b, c]):
		return False
	if a == 0 or b == 0 or c == 0:
		return False
	if a == b or b == c or a == c:
		return False
	return True

def check_solution(a, x, y, z):
	return (x*x + y*y - x*y - a*(z**3)) == 0

def main():
	border = "|"
	pr(border*72)
	pr(border, ".::   Hi all, she DID it, you should do it too! Are you ready? ::.  ", border)
	pr(border, "Welcome to the Ternary World! You need to pass each level until 20  ", border)
	pr(border, "to get the flag. Pay attention that your solutions should be nonzero", border)
	pr(border, "distinct integers. Let's start!                                     ", border)
	pr(border*72)

	level, step = 0, 19
	while level <= step:
		a = random.randint(2**(level * 12), 2**(level*12 + 12))
		equation = f'x^2 + y^2 - xy = {a}*z^3'
		pr(f"Level {level + 1}: {equation}")
		inputs = input().strip().split(",")
		try:
			x, y, z = map(int, inputs)
		except:
			die(border, "Invalid input, Bye!!")
		if check_inputs(x, y, z):
			if check_solution(a, x, y, z):
				pr(border, "Correct! Try the next level :)")
				level += 1
			else:
				pr(border, "You didn't provide the correct solution.")
				die(border, "Better luck next time!")			
		else:
			pr(border, "Your solutions should be non-zero distinct integers")
			die(border, "Quiting...")
		if level == step:
			pr(border, "Congratulations! You've successfully solved all the equations!")
			die(border, f"flag: {flag}")

if __name__ == '__main__':
	main()

是一道数学题，要求对不同尺寸的 20 个 $a$，找到满足式子的 $x^2+y^2-xy = az^3$ 三个变量 $x,y,z$ 其中要求这三个变量均不为0，且两两不相等。

一个很自然的想法，右边是 3 次，是一个奇数次，那么我们设 $z=a$，这样右边就是 $a^4$，要好看些。题目要求 $x,y$ 不能相等，但并没要求它们不能相反，所以令 $x=-y$，这样左边就是 $3y^2$，有一个系数，配合的还不是很好。

调整一下，我们设 $z=3a$，这样右边就是 $27a^4$，于是有 $3y^2=27a^4$ ，我们令 $y = 3a^2$ 就可以满足等式的要求了。

from pwn import *

context.log_level = 'debug'

def solve(a):
	z = 3*a
	y = 3*a**2
	x = -y
	return x,y,z

sh = remote("03.cr.yp.toc.tf","31317")

for _ in range(19):
	sh.recvuntil("x^2 + y^2 - xy = ")
	a = int(sh.recvuntil("*")[:-1])
	x,y,z = solve(a)
	sh.sendline(','.join(str(i) for i in [x,y,z]))


# | Correct! Try the next level :)
# | Congratulations! You've successfully solved all the equations!
# | flag: CCTF{T3rn3ry_Tr3x_3Qu4t!0n}

Keymote

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def gen_koymoted(nbit):
	p = getPrime(nbit)
	a, b = [randint(1, p - 1) for _ in '__']
	Ep = EllipticCurve(GF(p), [a, b])
	tp = p + 1 - Ep.order()
	_s = p ^^ ((2 ** (nbit - 1)) + 2 ** (nbit // 2))
	q = next_prime(2 * _s + 1)
	Eq = EllipticCurve(GF(q), [a, b])
	n = p * q
	tq = q + 1 - Eq.order()
	e = 65537
	while True:
		if gcd(e, (p**2 - tp**2) * (q**2 - tq**2)) == 1:
			break
		else:
			e = next_prime(e)
	pkey, skey = (n, e, a, b), (p, q)
	return pkey, skey

def encrypt(msg, pkey, skey):
	n, e, a, b = pkey
	p, q = skey
	m = bytes_to_long(msg)
	assert m < n
	while True:
		xp = (m**3 + a*m + b) % p
		xq = (m**3 + a*m + b) % q
		if pow(xp, (p-1)//2, p) == pow(xq, (q-1)//2, q) == 1:
			break
		else:
			m += 1
	eq1, eq2 = Mod(xp, p), Mod(xq, q)
	rp, rq = sqrt(eq1), sqrt(eq2)
	_, x, y = xgcd(p, q)
	Z = Zmod(n)
	x = (Z(rp) * Z(q) * Z(y) + Z(rq) * Z(p) * Z(x)) % n
	E = EllipticCurve(Z, [a, b])
	P = E(m, x)
	enc = e * P
	return enc

nbit = 256
pkey, skey = gen_koymoted(nbit)
enc = encrypt(flag, pkey, skey)

print(f'pkey = {pkey}')
print(f'enc = {enc}')

我们从加密 encrypt 函数开始看，

xp = (m**3 + a*m + b) % p 这里首先将 flag 放在了一条椭圆曲线上，作为 x 轴坐标 ，并且分别是在子群 p,q 下进行计算的。所以在后面使用了中国剩余定理来计算模 n 下曲线的 y 点，x = (Z(rp) * Z(q) * Z(y) + Z(rq) * Z(p) * Z(x)) % n

因此这一大部分的内容只是将 flag 放在一条模 $n$ 的椭圆曲线 $E$ 上作为 $P$ 点，随后加密计算得到 $enc = eP$。如果我们能够知道 $P$ 点的阶，我们直接对 $e$ 在该阶下求乘法逆元即可。但由于是模 $n$，这里我们没法计算。我们也需要先在子群 $p,q$ 下求出 $P$ 点的 $x$ 轴坐标，然后再用中国剩余定理进行组合。

那么我们就需要先分解 $n$，我们看到 gen_koymoted 函数。$n=p\cdot q$，其中 $p$ 是一个随机的素数，但注意到 $q = 2 \cdot _s + a$，而 _s = p ^^ ((2 ** (nbit - 1)) + 2 ** (nbit // 2))，是将 $p$ 的第一个比特和中间一个比特进行了翻转。可以表示为 $s=p-A$，于是有 $n=p\cdot q = p\cdot (2p-2A+a)=2p^2-p(2A-a)$，其中 $A$ 已知，$a$ 是一个较小的值（不超过10000），于是我们可以爆破 $a$ 然后解丢番图方程，从而求出 $p$。

from Crypto.Util.number import *
from gmpy2 import *

nbit = 256
p = getPrime(nbit)
_s = p ^ ((2 ** (nbit - 1)) + 2 ** (nbit // 2))

A = p-_s
n=6660938713055850877314255610895820875305739186102790477966786501810416821294442374977193379731704125177528590285016474818841859956990486067573436301232301
# f = 2p^2-p(2A-a)-n
for a in range(99999):
	delta = (2*A-a)**2+4*2*n
	if iroot(delta,2)[1]:
		delta = iroot(delta,2)[0]
		p = ((2*A-a)+delta)//4
		assert n%p==0
		print(p)
		print(n//p)

		# 93511613846272978051774379195449772332692693333173612296021789501865098047641
		# 71231138455229760679977773382211636812795966734548537479512744210680602878261

然后我们分别在子群 $p,q$ 下计算 $P$ 点，然后取其 $x$ 轴坐标，使用 CRT 获取 flag。

p = 93511613846272978051774379195449772332692693333173612296021789501865098047641
q = 71231138455229760679977773382211636812795966734548537479512744210680602878261
a = 5539256645640498184116966196249666621079506508209770360679460869295427007578
b = 20151017657582479433586370393795140515103572865771721775868586710594524816458
Q = (6641320679869421443758875467781930795132746694454926965779628505713445486895274490835545942727970688359873955019634877304270220728625521646208912044469433,2856872654927815636828860866843721158889474116106462420201092148493803550131351543372740950198853438539317164093538508795630146854596724019329887894933972)

Ep = EllipticCurve(GF(p),[a,b])

Qp = Ep(Q)
Epo = Qp.order()
Pp = Qp * inverse(65537,Epo)
mp = int(Pp.xy()[0])


Eq = EllipticCurve(GF(q),[a,b])
Qq = Eq(Q)
Eqo = Qq.order()
Pq = Qq * inverse(65537,Eqo)
mq = int(Pq.xy()[0])

m = crt([mp,mq],[p,q])
print(long_to_bytes(m))

# b'CCTF{a_n3W_4t7aCk_0n_RSA_a9ain!?\x82'

Bertrand

#!/usr/bin/env python3

import sys
import math
import functools
from PIL import Image
from random import randint
import string
from secret import flag, key, n

def pad(s, l):
	while len(s) < l:
		s += string.printable[randint(0, 61)]
	return s

def sox(n, d):
	x, y, t = 0, 0, d
	for s in range(n - 1):
		u = 1 & t // 2
		v = 1 & t ^ u
		x, y = spin(2**s, x, y, u, v)
		x += 2**s * u
		y += 2**s * v
		t = t // 4
	return x, y

def spin(n, x, y, u, v):
	if v == 0:
		if u == 1:
			x = n - 1 - x
			y = n - 1 - y
		x, y = y, x
	return x, y

def encrypt(msg, key, n):
	_msg = pad(msg, n ** 2)
	_msg, _key = [ord(_) for _ in _msg], [ord(_) for _ in key]
	img = Image.new('RGBA', (n, n), 'darkblue')
	pix = img.load()

	for _ in range(len(key)):
		w = len(_key)
		h = n**2 // w + 1
		arr = [[_msg[w*x + y] if w*x + y < n**2 else None for x in range(h)] for y in range(w)]
		_conf = sorted([(_key[i], i) for i in range(w)])
		_marshal = [arr[_conf[i][1]] for i in range(w)]
		_msg = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
		_msg = list(filter(lambda x: x is not None, _msg))
		_msg = [(_msg[_] + _key[_ % w]) % 256 for _ in range(n**2)]

	for d in range(n**2):
		x, y = sox(n, d)
		pix[x,y] = (_msg[d], _msg[d], _msg[d])
	keysum = sum(_key) if w > 0 else 0
	orient = keysum % 4
	img = img.rotate(90*orient)
	return img

assert len(key) == 3
img = encrypt(flag, key, n)
img.save('enc.png')

这道题目将 flag 的信息储存在了图片中，出题人对 python 语言的娴熟操作也令整个代码读起来会略微有点吃力，需要静下心来慢慢分析。我们先看到 encrypt 这个函数，

_msg = pad(msg, n ** 2)
_msg, _key = [ord(_) for _ in _msg], [ord(_) for _ in key]
img = Image.new('RGBA', (n, n), 'darkblue')
pix = img.load()
for _ in range(len(key)):

首先创建了一个 $n\times n$ 的图片，然后将 flag 填充至 $n\times n$ 的长度，随后分别用每个密钥进行处理，密钥未知，但是密钥的长度为3，并且使用了 ord 函数，说明每个密钥的值得范围是 $0-255$。

w = len(_key)
h = n**2 // w + 1
arr = [[_msg[w*x + y] if w*x + y < n**2 else None for x in range(h)] for y in range(w)]

将 msg 分为三块 arr，但是分块类似于栅栏加密，第一块为第 [0,3,6….] 个字节，第二块为第 [1,4,7….] 个字节 ，第二块为第 [2,5,8….] 个字节。

_conf = sorted([(_key[i], i) for i in range(w)])
_marshal = [arr[_conf[i][1]] for i in range(w)]

对密钥的大小进行排序，并记录原来的位置，例如原来有 key = [123,251,34]，排序后为 conf = [(34, 2), (123, 0), (251, 1)]

随后置换消息块 arr 进行置换，规则按照 key 来，按照上面的例子，那么置换后的消息块为 arr[2],arr[0],arr[1]

_msg = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
_msg = list(filter(lambda x: x is not None, _msg))
_msg = [(_msg[_] + _key[_ % w]) % 256 for _ in range(n**2)]

最后将三个数组拼接，并清除块中的 None 项，然后循环使用密钥逐元素进行模 256 加。

for d in range(n**2):
    x, y = sox(n, d)
    pix[x,y] = (_msg[d], _msg[d], _msg[d])
keysum = sum(_key) if w > 0 else 0
orient = keysum % 4
img = img.rotate(90*orient)
return img

如此操作三回后，将数组中的元素按一定规则放入图片中，最后根据三个密钥值的和来旋转图片。

这个 sox 规则可以本地用较小的数字测一下，发现就是希尔伯特曲线（但这并不是重点，我们也不需要逆，解密的时候再重新按照这个规则取点就好了）

那么想要恢复原来的图片的话，很直观的想法是爆破key，然后逆向解密：

1. 首先猜一个旋转角度，然后爆破key，求和后不符合我们设定的旋转角度的直接跳过（之所以先确定角度是因为按照希尔伯特曲线取点的操作很耗时，不能每次都取）
2. 调用 sox 函数从图片取得信息，随后循环执行步骤 3-5三次：
3. 循环使用密钥在模 256 下减
4. 根据 “key 的大小关系” 反向置换
5. 根据 “栅栏分块” 反向置换
6. 取消息开头判断是不是 “CCTF”
7. 无解的话换一个旋转角度，重新回到步骤 2

理论可行，但是实践起来，发现运行起来非常耗时，一个角度都需要爆破十几个小时（用python的话）。春哥的解决方案是 C++，沛公选择了部分数据，看了下 maple 的解决方案，是 z3 ！！！这种办法要简单很多了。因为所有的操作都是线性的，用 z3 去约束确实是可行的。

我们只需要爆破角度（一共四种），然后遍历 key 元素之间的大小关系（一共六种），然后按照加密规则进行操作，最后添加约束（用我们已知的 flag 头 ”CCTF{“ )即可。优雅，太优雅了！

# https://blog.maple3142.net/2023/07/09/cryptoctf-2023-writeups/#bertrand
import sys
import math
import functools
from PIL import Image
from random import randint
import string
import itertools
import z3


def pad(s, l):
    while len(s) < l:
        s += string.printable[randint(0, 61)]
    return s


def sox(n, d):
    x, y, t = 0, 0, d
    for s in range(n - 1):
        u = 1 & t // 2
        v = 1 & t ^ u
        x, y = spin(2**s, x, y, u, v)
        x += 2**s * u
        y += 2**s * v
        t = t // 4
    return x, y


def spin(n, x, y, u, v):
    if v == 0:
        if u == 1:
            x = n - 1 - x
            y = n - 1 - y
        x, y = y, x
    return x, y


n = 256
img = Image.open("enc.png")
img = img.rotate(90 * 1)  # guess
pix = img.load()
msg = []
for d in range(n**2):
    x, y = sox(n, d)
    msg.append(pix[x, y][0])


def try_conf(conf):
    key_sym = [z3.BitVec("key_%d" % i, 8) for i in range(3)]
    msg_sym = [z3.BitVec("msg_%d" % i, 8) for i in range(n**2)]
    msg_arr = msg_sym[:]
    for _ in range(len(key_sym)):
        w = len(key_sym)
        h = n**2 // w + 1
        arr = [[msg_arr[w * x + y] if w * x + y < n**2 else None for x in range(h)] for y in range(w)]
        _marshal = [arr[conf[i]] for i in range(w)]
        msg_arr = functools.reduce(lambda a, r: a + _marshal[r], range(w), [])
        msg_arr = list(filter(lambda x: x is not None, msg_arr))
        msg_arr = [(msg_arr[_] + key_sym[_ % w]) % 256 for _ in range(n**2)]
    sol = z3.Solver()
    for i in range(n**2):
        sol.add(msg_arr[i] == msg[i])
    for x, y in zip(msg_sym, b"CCTF{"):
        sol.add(x == y)
    if sol.check() == z3.sat:
        m = sol.model()
        print([m.eval(x) for x in key_sym])
        print(bytes([m.eval(x).as_long() for x in msg_sym])[:100])


for conf in itertools.permutations(range(3)):
    # correct conf = (1, 2, 0)
    print(conf)
    try_conf(conf)

    
(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
[107, 51, 89]
b'CCTF{3nCrypTioN_8Y_c0lUmn4R_7rAnSp05it!On!}9BB5bgJN8YNH2kRMynPqDmygUHsNCOoYAfn865iLVDKUBQhNuVfnQK65p'
(2, 0, 1)
(2, 1, 0)

Hard

Big

#!/usr/bin/env sage

from Crypto.Util.number import *
from hashlib import sha512
from flag import flag

def genkey(nbit):
	while True:
		p = getPrime(nbit)
		if p % 4 == 3:
			q = int(str(p)[::-1])
			if isPrime(q):
				return p * q, (p, q)

def setup(msg, pkey):
	hid = sha512(msg).digest()
	while True:
		a = bytes_to_long(hid)
		if kronecker(a, pkey) == 1:
			return a
		else:
			hid = sha512(hid).digest()

def encrypt(msg, pkey):
	a, m = setup(msg, pkey), bytes_to_long(msg)
	B, C = bin(m)[2:], []
	for b in B:
		while True:
			t = randint(1, pkey)
			if kronecker(t, pkey) == 2 * int(b) - 1:
				C.append((t - a * inverse(t, pkey)) % pkey)
				break
	return (a, C)


pkey, privkey = genkey(512)
E = encrypt(flag, pkey)

print(f'pkey = {pkey}')
print(f'E = {E}')

题目给出了一个 $n=p \cdot q$，其中满足 $p \equiv 3 \pmod 4$，并且 $p,q$ 的十进制数是前后相反的。那么首先我们就需要根据这个特性去将 $p,q$ 给恢复出来。掏出板子（其实就是加了约束的爆破）

from Crypto.Util.number import *
from random import randint
from math import *
# https://kt.gy/blog/2015/10/asis-2015-finals-rsasr/

def t(a, b, k):
	# sqrt(n) has 154 digits, so we need to figure out 77 digits on each side
    if k == (ndigs+1)//2:
        if a*b == n:
          print('p = %d' % a)
          print('q = %d' % b)
        return
    for i in range(10):
        for j in range(10):
			# we try to guess the last not-already-guessed digits of both primes
            a1 = a + i*(10**k) + j*(10**(ndigs-k))
            b1 = b + j*(10**k) + i*(10**(ndigs-k))
            if a1*b1 > n:
				# a1 and b1 are too large
                continue
            if (a1+(10**(ndigs-k)))*(b1+(10**(ndigs-k))) < n:
				# a1 and b1 are too small
                continue
            if ((a1*b1)%(10**(k+1))) != (n%(10**(k+1))):
				# The last digits of a1*b1 (which won't change later) doesn't match n
                continue
			# this a1 and b1 seem to be a possible match, try to guess remaining digits
            t(a1, b1, k+1)

n = 72271787633166084700895603235291055045699965307538401174867474485084272711938364003794151073975875159886045553516299177522950407802715116792937858353646755246888532333536918663888208381012106370000886903776721867958523682675624556576505534100750339626081218194389244007622749982917071344697799413034317147013
ndigs = len(str(isqrt(n)))-1
t(0, 0, 0)

p = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
q = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967

随后的加密是逐比特的，使用了 kronecker symbol：是勒让德符号以及雅可比符号的推广，将底数由正奇数推广至一切整数。因此就是数的二次剩余性质。密文 $c_i \equiv t_i-\frac{a}{t_i}$ 组成，其中，如果$m_i = 0$， 则 $t_i$ 在模 $n$ 下是二次非剩余，如果$m_i = 1$， 则 $t_i$ 在模 $n$ 下是二次剩余。由于 $a$ 已知，所以我们有一个关于 $t_i$ 的一元二次同余式：$t_i^2 -c_it_i+a \equiv 0 \pmod n$，但理论上 $t_i$ 会有四个解，这四个 $t_i$ 的二次剩余性质是否一致呢？测一下

from Crypto.Util.number import *

while True:
	p = getPrime(128)
	q = getPrime(128)
	pkey = p*q
	if p%4==3 and q%4==3:
		break

def qsqrt(s,p):
	return pow(s,(p+1)//4,p)

while True:
	a = randint(1, pkey)
	if kronecker(a, pkey) == 1:
		break

for _ in range(100):
	t = randint(1, pkey)
	if kronecker(t, pkey) == 1:
		c =(t - a * inverse(t, pkey)) % pkey
		tp = (qsqrt(c^2+4*a,p)+c)/2
		tq = (qsqrt(c^2+4*a,q)+c)/2
		ti = crt([int(tp),int(tq)],[p,q])
		print(kronecker(ti, pkey))

代码中我只计算了四个解中的一个，但是所有的返回结果均显示 kronecker(ti, pkey)=1，也就是说，四个解均为二次剩余。因此我们只需要使用所有的 $c_i$，分别解出 $t_i$ ，判断其是否为二次剩余即可得到 flag。

p = 9397241380094769307017158485931177341961951476061947013977394739417988689050439874435488908822482074028128151771446818457295188445665208696820950505470967
q = 7690745050590286968025665448815927548186441771518218204702842288098845344789340509868897149374937793107491606741591691437711395848517107039674900831427939
a = 8288287062919561222859437914506472745100526530793196302687340335555115611914901909767968051705772262896385459058120439118678774481183385263128414336707441
C = [...]
flag = ""
for c in C:
	tp = (qsqrt(c^2+4*a,p)+c)/2
	tq = (qsqrt(c^2+4*a,q)+c)/2
	ti = crt([int(tp),int(tq)],[p,q])
	flag += "1" if kronecker(ti, p*q)==1 else "0"
print(long_to_bytes(int(flag,2)))


# b'CCTF{_Cocks_18e_5chEm3}'

Byeween

[root@VM-0-7-centos 2023CCTF]# nc 03.cr.yp.toc.tf 33137
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hi all, I have created a basic and simple cryptography task about   |
|  elliptic curve over rational field. Your mission is to find all     |
|  points Q over E such that 2 * Q = P, such that P is given.          |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating parameters, please wait...
| Options: 
|	[I]informations 
|	[S]ubmit points 
|	[Q]uit
I
| E = Elliptic Curve defined by y^2 = x^3 - 342446165721*x over Rational Field
| Q = (11312349909982661811485861119060804225/19331014841872758669209197674496 : 116099721688697073463805997395884506343692166552542145/84992769577026199814140167579218475635959660544 : 1)
| Options: 
|	[I]informations 
|	[S]ubmit points 
|	[Q]uit

题目给定一条实数域下的曲线，然后需要我们给出点 $Q$ 满足 $2Q=P$ ，理论上来说在有理数域上这条曲线上应该是有无穷多点的，因此我们也不能求 $2$ 在曲线阶下的逆来解题。不过sagemath有一个现成的函数，我们在 SEECTF里面的 Isogeny Maze 一题也是遇到过的，就是 division_points

于是

E = EllipticCurve(QQ,[-305870939136,0])
Q = E(221303102265244533371483402644506621479115743892744422261154252676217167681/213693626187627681294262261815109614857458011180352878308546312436900,2783390608443160879347865193209570334025777278259973486688917132185180217527312885060303635922214606854675997921/3123829724421951797186354163467857827737536183310312285378057065885446059832209901960648225147252153000)
Q.division_points(2)

[(-581886118964997/2395417249 : -30763025733327911831808/117238906417807 : 1),
 (-45549205864448/188320729 : 677260204084819298944/2584325364067 : 1),
 (5454365075973/3869089 : -11589081804276058368/7610498063 : 1),
 (3920272615593/2768896 : 7067979399917751147/4607442944 : 1)]

交互

s
| Please send the points on elliptic curve one by one: 
-581886118964997/2395417249,-30763025733327911831808/117238906417807
| You have sent 1 correct points already!
| Options: 
|	[I]informations 
|	[S]ubmit points 
|	[Q]uit
s
| Please send the points on elliptic curve one by one: 
-45549205864448/188320729,677260204084819298944/2584325364067
| You have sent 2 correct points already!
| Options: 
|	[I]informations 
|	[S]ubmit points 
|	[Q]uit
s
| Please send the points on elliptic curve one by one: 
5454365075973/3869089,-11589081804276058368/7610498063
| You have sent 3 correct points already!
| Options: 
|	[I]informations 
|	[S]ubmit points 
|	[Q]uit
s
| Please send the points on elliptic curve one by one: 
3920272615593/2768896,7067979399917751147/4607442944
| Congrats, you got the flag: b'CCTF{H4lVin9_pO!ntS_0n_3lLipT1C_cuRve5!}'

也许出题人本意是让我们自己实现叭，故放在了 hard 难度，没想到 sagemath 就有现成的实现。

Majan

#!/usr/bin/env sage

import sys
from Crypto.Util.number import *
from hashlib import sha256
from flag import flag


p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
G = E.random_point()
_o = E.order()
original_msg = 'I love all cryptographers!!!'

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def keygen(E):
	skey = randint(1, _o)
	pkey = skey * G
	return pkey, skey

def encrypt(msg, pkey):
	e, l = randint(1, _o), len(msg)
	m1, m2 = bytes_to_long(msg[:l // 2]), bytes_to_long(msg[l // 2:])
	assert m1 < p and m2 < p
	e1, e2 = (e * pkey).xy()
	c1, c2 = m1 * e1 % p, m2 * e2 % p
	return (c1, c2, e * G)

def sign(msg, skey):
	_tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
	while True:
		K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
		r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
		if r * s != 0:
			break
	h = bytes_to_long(sha256(msg).digest())
	t = inverse(K[0], _o) * (h * r - s * skey) % _o
	return (r, s, t)

def verify(msg, pkey, _sign):
	r, s, t = [int(_) % _o for _ in _sign]
	h = bytes_to_long(sha256(msg.encode('utf-8')).digest())
	u = int(h * r * inverse(t, _o) % _o)
	v = int(s * inverse(t, _o) % _o)
	# u = h * r * inverse(t, _o) % _o
	# v = s * inverse(t, _o) % _o
	_R = (u * G - v * pkey).xy()[0]
	return _R == r

def main():
	border = "|"
	pr(border*72)
	pr(border, "Hi all, now it's time to solve a probably simple ECC challenge about", border)
	pr(border, "encryption and signing in elliptic curves! Follow the questions and ", border)
	pr(border, "find the secret flag, are you ready!?                               ", border)
	pr(border*72)

	pkey, skey = keygen(E)

	while True:
		pr("| Options: \n|\t[E]ncrypt a message! \n|\t[G]et the flag \n|\t[P]ublic Key \n|\t[S]ign a message \n|\t[V]erify signature \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 'e':
			pr(border, 'Send your message here: ')
			_msg = sc()
			_enc = encrypt(_msg, pkey)
			pr(border, f'enc = {_enc}')
		elif ans == 'g':
			pr(border, 'You should send the valid signature for my given message!')
			pr(border, 'Send the signature of original message here: ')
			_sgn = sc().split(b',')
			try:
				_sgn = [int(_) for _ in _sgn]
				if verify(original_msg, pkey, _sgn):
					die(border, f'Congratz! You got the flag: {flag}')
				else:
					pr(border, 'Your signature is not correct!')
			except:
				import traceback; traceback.print_exc()
				pr(border, 'Try to send valid signature!')
				continue
		elif ans == 's':
			pr(border, 'Send your message to sign: ')
			_msg = sc()
			if len(_msg) >= 10:
				die(border, 'Sorry, I sign only short messages! :/')
			_sgn = sign(_msg, skey)
			pr(border, f'sgn = {_sgn}')
		elif ans == 'v':
			pr(border, 'Send your signature to verify: ')
			_sgn = sc().split(b',')
			try:
				_sgn = [int(_) for _ in _sgn]
				pr(border, 'Send your message: ')
				_msg = sc()
				if verify(_msg, pkey, _sgn):
					pr(border, 'Your message successfully verified :)')
				else:
					pr(border, 'Verification failed :(')
			except:
				pr(border, 'Try to send valid signature!')
				continue
		elif ans == 'p':
			pr(border, f'pkey = {pkey}')
			pr(border, f'G = {G}')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

题目是基于 ECC 的加密、签名系统，提供四个服务

1. 提供加密服务
2. 提供签名服务，但是签名的数据长度不能超过 10
3. 提供验签服务
4. 如果提供的签名是消息 I love all cryptographers!!! 的签名，则给出 flag。

注意到由于签名服务限制了消息长度，我们无法直接让服务端给我们计算 I love all cryptographers!!! 的签名，那么应该是利用其他服务来获取服务端的私钥，然后自己计算签名。

def encrypt(msg, pkey):
	e, l = randint(1, _o), len(msg)
	m1, m2 = bytes_to_long(msg[:l // 2]), bytes_to_long(msg[l // 2:])
	assert m1 < p and m2 < p
	e1, e2 = (e * pkey).xy()
	c1, c2 = m1 * e1 % p, m2 * e2 % p
	return (c1, c2, e * G)

加密算法 encrypt：

输入： $m,pubkey$

$e \in (1,_o)$

$(e_1,e_2) = e\cdot pkey = e \cdot sk \cdot G$

$c_1 \equiv m_1\cdot e_1 \pmod p,c_2 \equiv m_2\cdot e_2 \pmod p$

输出 $c_1,c_2,e\cdot G$

根据加密逻辑，我们可以利用加密服务，比如传一个 '\x01\x01'，就能获得 $e_1,e_2$，于是我们就能获得 $(e_1,e_2)=e\cdot sk\cdot G$，我们还知道 $e\cdot G$，如果能解 ECDLP，就能够计算 $sk = log_{eG}(e\cdot sk\cdot G)$ ，从而获取私钥了，不过显然难度为 hard 题，不会提供一个能直接解 ECDLP 的题，我们看看别处。

def sign(msg, skey):
	_tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
	while True:
		K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
		r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
		if r * s != 0:
			break
	h = bytes_to_long(sha256(msg).digest())
	t = inverse(K[0], _o) * (h * r - s * skey) % _o
	return (r, s, t)

签名算法 sign

输入：$m$

$K =[k_0+tail,k_1+tail] $

$r = K_0 G.x$

$s=K_1G.x$

$h = sha256(msg)$

$t \equiv \frac{h\cdot r-s\cdot skey}{K_0} \pmod {_o}$

输出：$(r,s,t)$

那么这里很显然有一个出题人故意设置的点，就是 $K_0,K_1$ 的长度是比较短的，（因为 $K$ 整除了 1<<24 ），我们还能不断的调用签名函数，这就不由让人想到 HNP 了。然后想，如果我们能够解决 HNP，那么我们就能恢复 $K_0$，然后就能利用 $t,h,r,s$ 恢复私钥 $skey$ 了，那就结束了！

那么想一下如果构造来解这样一个 HNP，根据 $t$ 的生成公式，

我们有 $K_0 \equiv t^{-1}\cdot h\cdot r-t^{-1} \cdot s\cdot skey \pmod o$，

其中 $r,s,t$ 已知，

我们设 $A = -t^{-1}\cdot s，B = t^{-1}\cdot h\cdot r,$，

于是有 $K_0 = A\cdot skey+B + kp$

很像最开始接触 HNP 遇到的祥哥（Soreat_u）出的一道题 XCTF2020-高校战役-NHP)，那个题也是不断交互，需要拿到临时密钥比较短的签名。

这里我们构造经典的 HNP 格子，其中 $K = 2^{231}$

$M =
\begin{bmatrix}
o & & & & & & \newline
& o & & & & & \newline
& &\ddots& & & & \newline
& & & o & & & \newline
A_0&A_1&\dots & A_t&K/o& & \newline
B_0&B_1&\dots & B_t& & K & \newline
\end{bmatrix}$

然后这里就会存在一个向量 $v = \begin{bmatrix} k_0 & k_1 & \cdots & k_t & skey & 1 \end{bmatrix}$

使得 $vM = \begin{bmatrix} K_0 & K_1 & \cdots & K_t & skey\cdot K/o & K \end{bmatrix}$

再消去 $K/o$ ，我们就能直接获取到 $skey$ 了。

from hashlib import sha256
from Crypto.Util.number import *
context.log_level = 'debug'
p = 114863632180633827211184132915225798242263961691870412740605315763112513729991
A = -3
B = 105675527217961035404524512435875047840495516468907806313576241823653895562912
E = EllipticCurve(GF(p), [A, B])
G = E.random_point()
o = _o = E.order()
original_msg = b'I love all cryptographers!!!'

local = False
if not local:
    from pwn import *

    sh = remote('06.cr.yp.toc.tf','13337')
    sh.recvuntil("[Q]uit\n")
    sh.sendline("P")
    sh.recvuntil("| pkey = (")
    x = int(sh.recvuntil(" : ")[:-3])
    y = int(sh.recvuntil(" : ")[:-3])
    pubkey = E(x,y)

    sh.recvuntil("G = (")
    x = int(sh.recvuntil(" : ")[:-3])
    y = int(sh.recvuntil(" : ")[:-3])
    G = E(x,y)
    print(pubkey,G)

def get_sign(msg):
    sh.recvuntil("[Q]uit\n")
    sh.sendline("S")
    sh.recvuntil("sign: ")
    sh.sendline(msg)
    sh.recvuntil('sgn = ')
    sig = eval(sh.recvuntil(")"))
    return sig

def sign(msg, skey):
    _tail = bytes_to_long(sha256(str(skey).encode('utf-8')).digest()) % (1 << 24)
    while True:
        K = [randint(1, 2**255) // (1 << 24) + _tail for _ in '__']
        r, s = int((K[0] * G).xy()[0]), int((K[1] * G).xy()[1])
        if r * s != 0:
            break
    h = bytes_to_long(sha256(msg).digest())
    t = inverse(K[0], _o) * (h * r - s * skey) % _o
    return (r, s, t)


def keygen(E):
    skey = randint(1, _o)
    pkey = skey * G
    return pkey, skey

if local:
    pubkey, skey = keygen(E)


A = []
B = []
times = 0
while len(A)<40:
    print(len(A))
    try:
        times+=1
        if not local:
            r,s,t = get_sign(str(times).encode())
        else:
            r,s,t = sign(str(times).encode(),skey)
        h = bytes_to_long(sha256((str(times)+"\n").encode('utf-8')).digest())	# 这里好坑，我卡了好久，本地都能成功，远程就是失败，一直找不到原因，最后才意识到可能是 hash 算错了。
        A.append(int((-inverse(t,o)*s)%o))
        B.append(int(inverse(t,o)*h*r%o))
    except Exception as e:
        print(str(e))
        pass


print("construct hnp lattice...")
CC = matrix(QQ,[A,B])
K = 2^232
DD = matrix(QQ,[[K/o,0],[0,K]])
MM = block_matrix(QQ,[[o,0],[CC,DD]])
L = MM.LLL()

for each in L:
    if abs(each[-1]) == K:
        if each[-2] * o % K == 0:
            print(each)
            ss = (each[-2] * o // K)%o
            # skey = abs(skey)
            print(pubkey == ss*G)
            signatrue = sign(original_msg, ss)
            sh.recvuntil("[Q]uit\n")
            sh.sendline("G")
            sh.recvuntil("message here: ")
            sh.sendline(','.join(str(i)for i in signatrue))
            sh.interactive()

            # print(int(each[0]).bit_length(),skey)
        
[DEBUG] Received 0x46 bytes:
    b"| Congratz! You got the flag: b'CCTF{L4T71c3_atTAck5_a9A!nS7_ECDSA!}'\n"
| Congratz! You got the flag: b'CCTF{L4T71c3_atTAck5_a9A!nS7_ECDSA!}'

比较坑的一个点是，服务端在接受用户的输入的时候，把回车符号也算进去了，所以本地在计算 $h$ 的时候需要注意。

Vinefruit

#!/usr/bin/env python3

import sys
import random
import binascii
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def vinefruit(msg, mod, flag = 0):
	P = [16777619, 1099511628211, 309485009821345068724781371]
	O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
	assert mod in [0, 1, 2]
	p, o, m = P[mod], O[mod], 2 ** (2 << (4 + mod))
	vine = o
	for b in msg:
		if flag == 1:
			vine = (vine + b) % (2 ** 128)
		else:
			vine = vine ^ b
		vine = (vine * p) % m
	return vine

def main():
	border = "|"
	pr(border*72)
	pr(border, " Hi all, I have designed a gorgeous cryptography hash function in   ", border)
	pr(border, " order to secure the world! Your mission is to find collision for   ", border)
	pr(border, " this function with specific conditions.                            ", border)
	pr(border*72)
	
	step = 19

	while True:
		pr("| Options: \n|\t[S]ubmit collision \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 's':
			S = []
			for level in range(step):
				mod = random.randint(0, 2)
				pr(border, f'Submit two different string such that vinefruit(m1, {mod}, 1) = vinefruit(m2, {mod}, 1)')
				pr(border, f'You are at level: {level + 1}')
				if level == step - 1 and len(S) == step - 1:
					die(border, f'Congrats, you got the flag: {flag}')
				try:
					pr(border, f'Please send first byte string: ')
					s1 = sc()[:-1]
					pr(border, f'Please send second byte string: ')
					s2 = sc()[:-1]
					s1, s2 = binascii.unhexlify(s1), binascii.unhexlify(s2)
				except:
					pr(border, 'You should send valid hex strings.')
					break
				if len(s1) == len(s2) == 35 - level and s1 != s2:
					if vinefruit(s1, mod, 1) == vinefruit(s2, mod, 1):
						if vinefruit(s1, mod, 1) not in S:
							S.append(vinefruit(s1, mod, 1))
							pr(border, 'gj, try the next level :)')
						else:
							break
					else:
						break
				else:
					die(border, 'Kidding me?! Try again and be smart!! Bye!!!')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

简而言之，服务端每次指定一个 mod，mod 会确定 o,p,m，我们需要找到两个指定长度的不同消息 $S_1,S_2$，满足 $f(S_1) \equiv f(S_2) \pmod m$，设 $S=m_l||m_{l-1}||\cdots||m_1$ ，那么有 $f(S)\equiv \sum_{i=1}^n m_i \cdot p^i \pmod m$

其实这和我们在 SEECTF 遇到的 onelinecrypto 差不多，那一题是要求 $f(S) \equiv 0 \pmod {13^{37}}$，并且还要求 $S$ 都是可见字符，而这一题约束就要松的多了，因此这里也不需要用到枚举，我也是照搬脚本，只是稍微改了改交互。

import string
import re


avg = 127

def attack(mod,level):

    P = [16777619, 1099511628211, 309485009821345068724781371]
    O = [2166136261, 14695981039346656037, 144066263297769815596495629667062367629]
    p, o, m = P[mod], O[mod], 2 ** (2 << (4 + mod))
    M = m

    length = 35 - level
    P = PolynomialRing(ZZ, "ap", length)
    aps = P.gens()
    aa = [ap + avg for ap in aps]
    f = sum([a * p**(i+1) for i, a in enumerate(aa)]) + o - length

    L = matrix(f.coefficients()).T
    L = block_matrix([[1,L],[0,M]])
    scale = [1]*(length+1) + [2**20]
    Q = diagonal_matrix(scale)
    L *= Q
    L = L.BKZ(block_size=25)
    L /= Q

    answer = []

    for row in L:
        if row[-2] < 0:
            row = -row
        if row[-1] == 0 and row[-2] == 1:
            #print(row)
            assert f(*row[:-2]) % M == 0
            aa = [x + avg for x in row[:-2]][::-1]
            if bytes(aa).hex() not in answer:
                answer.append(bytes(aa).hex())
                if len(answer) == 2:
                    return answer
from pwn import *

sh = remote("04.cr.yp.toc.tf","31777")
sh.recvuntil("[Q]uit")
sh.sendline("S")
for level in range(19):
    sh.recvuntil("vinefruit(m1, ")
    mod = int(sh.recvuntil(",")[:-1])
    answer = attack(mod,level)
    sh.recvuntil("string: ")
    sh.sendline(answer[0])
    sh.recvuntil("string: ")
    sh.sendline(answer[1])

# [DEBUG] Received 0xcd bytes:
#     b'| gj, try the next level :)\n'
#     b'| Submit two different string such that vinefruit(m1, 0, 1) = vinefruit(m2, 0, 1)\n'
#     b'| You are at level: 19\n'
#     b"| Congrats, you got the flag: b'CCTF{fINd1n9_cOlL!s10n_f0r___FNV2___!}'\n"

Shevid

#!/usr/bin/env sage

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5
from flag import flag

def gen_param(B):
	while True:
		a = randint(B >> 1, B)
		b = randint(B >> 2, B >> 1)
		p = 2**a * 3**b - 1
		if is_prime(p):
			return a, b

def gen_dmap(E):
	return E.isogeny(E.lift_x(ZZ(1)), codomain = E)

def gen_tpt(E, a, b):
	P, Q = [((p + 1) // 2**a) * _ for _ in E.gens()]
	R, S = [((p + 1) // 3**b) * _ for _ in E.gens()]
	return P, Q, R, S

def keygen(EC, b, P, Q, R, S):
	skey = randint(1, 3**b)
	T = R + skey * S
	phi = EC.isogeny(T, algorithm = "factored")
	_phi_dom, _phi_P, _phi_Q = phi.codomain(), phi(P), phi(Q)
	return skey, _phi_dom, _phi_P, _phi_Q

a, b = gen_param(190)
p = 2**a * 3**b - 1

F.<x> = GF(p^2, modulus = x**2 + 1)
EC = EllipticCurve(F, [0, 6, 0, 1, 0])
P, Q, R, S = gen_tpt(EC, a, b)

print(f'P = {P.xy()}')
print(f'Q = {Q.xy()}')
print(f'R = {R.xy()}')
print(f'S = {S.xy()}')

skey, _phi_dom, _phi_P, _phi_Q = keygen(EC, b, P, Q, R, S)

print(f'_phi_dom = {_phi_dom}')
print(f'_phi_P   = {_phi_P.xy()}')
print(f'_phi_Q   = {_phi_Q.xy()}')

key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
enc = cipher.encrypt(flag)

print(f'enc = {enc.hex()}')

题目又是基于超椭（超奇异椭圆曲线），参数这边，$p=2^a3^b-1$，根据曲线 phi 给出的 $p$ ，我们能够得到 $a=142,b=69$。然后还给出了 四个点 $P,Q,R,S$ ，其中 $P,Q$ 的阶是 $2^a$，$R,S$ 的阶是 $3^b$

然后随机生成私钥 $skey \in (0,3^b) $，计算 $T = R+skey\times S$ ，并以 T 为核对曲线 $E$ 进行同源映射到曲线 $phi$，随后给出曲线 $phi$，以及给出 $P,Q$ 在曲线 $phi$ 上的象: $phi(P),phi(Q)$

我们需要根据这些信息来恢复 $skey$。

我对超椭同源这块还很陌生，一个初步的想法应该是根据 $phi$ 和 $E$ 能够恢复出核 $T$，然后减去 $R$，求个 $ECDLP$ 得到 $skey$ 。（当然这只是个小白的痴心妄想）

实在不会做，只能踩在巨人的肩膀上了，github上有相关攻击的开源代码

# Local imports
import public_values_aux
from public_values_aux import *

# Load Sage files
load('castryck_decru_shortcut.sage')

# Baby SIKEp64 parameters
a = 142
b = 69

# Set the prime, finite fields and starting curve
# with known endomorphism
p = 2^a*3^b - 1
public_values_aux.p = p

Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2) # Speeds things up in Sage

# Generation of the endomorphism 2i
two_i = generate_distortion_map(E_start)

# Generate public torsion points, for SIKE implementations
# these are fixed but to save loading in constants we can
# just generate them on the fly
# P2, Q2, P3, Q3 = generate_torsion_points(E_start, a, b)
P = (3799366067639160994711391413511701264777392349807255916259320256251336249666*i + 633884628131689177031068067897867565283026098415356709331881575255526844055, 3967348484864888240941807454988077684669074109524399477973520952727771366997*i + 2712354532382043232096058211997452093712477916671679907467703464009558475387)
Q = (560486392227142181240528415381730657098132581407794833013161975335122628946*i + 3215971074127995409351672272900519761566156375365764079386358523254177565572, 2231746347912007096335360835242707156884468521076802738444724241125548841199*i + 1147378568798166954853288670809304301194478550602719730593160186622788033023)
R = (2656280316115888204975052029900945854050191685154131031859911335618240136443*i + 1127449111197960889758916770042950976852995868310602942974825430779982061546, 3477289737920472771668877366806058236254602770820629911886593813749930497839*i + 4646016633241840360901490323351236375375727836768954121794139000985805816564)
S = (2403139149412141532587482679318245468078604585804423116505024414375742701912*i + 2772488504607240668919423445309052101443116827322741849326656561794480962717, 3356599382898540527962106232860239304405841217130774924490318752448476310798*i + 2818004736373436361527915593539097434287090434842750370886675729711731978922)
P2, Q2, P3, Q3 = E_start(P), E_start(Q), E_start(R), E_start(S)

check_torsion_points(E_start, a, b, P2, Q2, P3, Q3)

# Generate Bob's key pair
# bob_private_key, EB, PB, QB = gen_bob_keypair(E_start, b, P2, Q2, P3, Q3)
EB = EllipticCurve(Fp2, [0,6,0,(2070374075904221348548347954672740119972290047985052548426161483408084160515*i+896749506444795652787374405713981306103783874504413776724865996633074195878),(2497300913991521538985990865799426081199023429830552981773916386651958830387*i+4243320791854592301388975795466391442631117041175807728844738724691845270777)])
EB.set_order((p+1)**2, num_checks=0)
PB   = EB(76437828586489590038329193939006186966443918785230388533883401536928551274*i + 1854701339851606878866613257086348330205980107370562791121360193846610915298, 3614996124089236146025194675467338095830005859290616536023140003816221458491*i + 1308394538776387115295908857102539180825411698539070801598965381200026966383)
QB   = EB(2350346337927935568113772636838467488287314266120334638991371449749383548230*i + 3389994457403704259291228848441313337916860864318549296438418403582347527289, 3514523396038039657181009561828298688334341559779027220238590888980836781356*i + 1132784636339236588815425424619354807485262558088269015122405460656452137103)

#solution = Integer(bob_private_key).digits(base=3)

print(f"Running the attack against Baby SIDHp64 parameters, which has a prime: 2^{a}*3^{b} - 1")
#print(f"If all goes well then the following digits should be found: {solution}")

# ===================================
# =====  ATTACK  ====================
# ===================================

def RunAttack(num_cores):
    return CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=num_cores)


recovered_key = RunAttack(4)

# Running the attack against Baby SIDHp64 parameters, which has a prime: 2^142*3^69 - 1
# Determination of first 2 ternary digits. We are working with 2^114-torsion.
# Testing digits: [2, 0]
# Testing digits: [1, 0]
# Testing digits: [0, 1]
# Testing digits: [0, 0]
# Testing digits: [0, 2]
# Testing digits: [1, 2]
# Testing digits: [2, 1]
# Testing digits: [1, 1]
# Testing digits: [2, 2]
# Computing image of 3-adic torsion in split factor CB
# Glue-and-split! These are most likely the secret digits.
# Bob's secret key revealed as: 35588822058809282635150734794357
# In ternary, this is: [2, 2, 2, 1, 2, 2, 2, 1, 1, 0, 0, 0, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 1, 1, 2, 2, 0, 1, 0, 1, 0, 0, 1, 2, 2, 1, 2, 2, 1, 2, 0, 0, 0, 1, 2, 0, 1, 2, 1, 1, 2, 0, 0, 1, 1, 0, 1]
# Altogether this took 8.304964780807495 seconds.

直接获得私钥，然后 AES 解密一下即可

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import md5

skey = 35588822058809282635150734794357

enc = '50d8ed352ccf3ce6d64b25e50ed67b832dcbcd94dcb7dc8293e813e0c83ace541abb61618d5f971ff5d24fab8a2e'
enc = bytes.fromhex(enc)


key = md5(long_to_bytes(skey)).digest()
iv = md5(str(skey).encode()).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
flag = cipher.decrypt(enc)

print(f'flag = {flag}')

# flag = b'CCTF{3FfiC!En7_k3Y_R3c0vErY_4tTacK_ON_SIDH!!!}'

Tough

Slowsum

#!/usr/bin/env sage

import sys
from itertools import product
from flag import flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def slowsum(p, n):
	g = 0
	perms = list(product([0, 1], repeat = n))
	for _prm in perms:
		g += p(_prm)
	return g

def h4sh(p, q):
	coeffs = p.coefficients()
	return pow(sum(coeffs), (q - 1) // 2 - sum(coeffs), q) 

def main():
	border = "|"
	pr(border*72)
	pr(border, "Hi all, I have created a basic and rudimentary version of a sumcheck", border)
	pr(border, "protocol. Your task is to generate a false statement and persuade   ", border)
	pr(border, "verifier of its validity.                                           ", border)
	pr(border*72)
	
	q = 2**61 - 1  # Mersenne prime
	F = GF(q)

	while True:
		pr("| Options: \n|\t[C]laim the statement \n|\t[D]etermine parameters and polynomial \n|\t[Q]uit")
		ans = sc().decode().lower().strip()
		if ans == 'd':
			pr(border, f'Please first send the number of variable and the degree of your desired polynomial:')
			_ans = sc()
			try:
				_n, _d = [int(_) for _ in _ans.split(b',')]
				if (_n * _d) // q < 5e-17 and _n >= 5 and _d >= 3:
					R = PolynomialRing(F, _n, 'x')
					x = R.gens()
				else:
					raise Exception()
			except:
				die(border, 'The parameters are not consistent! Try again!!')
			pr(border, f'Now, please send the {_n}-variable polynomial as p: ')
			_p = sc().strip().decode()
			try:
				_p = R(_p)
				p = _p
				_deg = _p.degree(std_grading=True)
				if _deg != _d:
					raise Exception()
			except:
				die(border, 'The polynomial is not valid or does not hold true in the given situations!')
			g = slowsum(_p, _n)
		elif ans == 'c':
			pr(border, 'Please send the g: ')
			_g = sc()
			try:
				_g = int(_g)
				if _g == g:
					die(border, 'Kidding me?! Bye :P')
			except:
				die(border, 'Some exception occurred! Bye!!')
			_P, _H = [], []
			for i in range(_n):
				pr(border, f'Please send the (p_{i}, h4sh(p_{i}, q)): ')
				pr(border, f'Note that the variable of p_{i} should be x. ')
				_ph = sc().strip()
				try:
					_p, _h = [_.decode() for _  in _ph.split(b',')]
					_R = PolynomialRing(F, 'x')
					_p, _h = _R(_p), F(_h)
					if _p.degree() > _d:
						raise Exception()
					_P.append(_p)
					_H.append(_h)
				except:
					die(border, 'Some exception occurred! Bye!!')
			j = 0
			for i in range(_n):
				if i == 0:
					if _P[i](0) + _P[i](1) != _g or h4sh(_P[i], q) != _H[i]:
						break
				else:
					if _P[i](0) + _P[i](1) != _P[i-1](_H[i-1]) or h4sh(_P[i], q) != _H[i]:
						break
				j += 1
			if j < _n or p(_H) != _P[_n-1](_H[_n-1]):
				die(border, 'Oops, verifier believes that the polynomial is not valid! Bye!!')
			die(border, f'Congrats, here the flag: {flag}')
		elif ans == 'q':
			die(border, 'Quitting...')
		else:
			die(border, 'You should select valid choice!')

if __name__ == '__main__':
	main()

这道题的流程看起来比较复杂冗长，我们一点点走下来。

首先看到 [D]etermine parameters and polynomial：我们需要给服务提供一个多项式，不过在此之前，我们要先如果这个多项式的变量数量和度（degree)，其中，需要满足 if (_n * _d) // q < 5e-17 and _n >= 5 and _d >= 3:，那么我们这里就先设定 $n=5,d=3$ ，然后我们给出的多项式为 x0^3 (他好像只判断了最高次，并没有判断变量数量，所以方便起见，我们先给一项，往后看看先)，然后执行 g = slowsum(_p, _n)

def slowsum(p, n):
	g = 0
	perms = list(product([0, 1], repeat = n))
	for _prm in perms:
		g += p(_prm)
	return g

slowsum 会让每个变量都遍历一遍 0，1 然后相加。由于这里我们的多项式只有一个变量，因此求和结果应该是 $g=2^4 = 16$

然后我们看到 [C]laim the statement：我们先给一个不等于前面 $g$ 的值 $_g$ （我们可以给个 0 先），

然后要给 $n=5$ 对单项式和值 p_{i}, h4sh(p_{i}, q)，（我们可以给5个 x^3,1 先）

接下来要过几个判断：

当 $i=0$ , 对于每个单项式 $p(x)$，都要有 $p_0(0)+p_0(1)=_g$ 以及 h4sh(_P[i], q) = _H[i] ，后面这部分我们只要按照它的要求生成 即可，前面这部分，我们把前面的设成 $_g=1$ 好了。

当 $i\gt0$，对于每个单项式 $p(x)$，都要有 $p_i(0)+p_i(1)=p_{i-1}(H_{i-1})$ 以及 h4sh(_P[i], q) = _H[i] ，好像这个我们能过，因为 $H_{i-1}$ 一直是 1，$p_i(0)=0$，

最后，要求 p(_H) == _P[_n-1](_H[_n-1])，对于我们这就是 $1^3=p_4(1)=1$，好像也能过。验证一下，

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Hi all, I have created a basic and rudimentary version of a sumcheck |
| protocol. Your task is to generate a false statement and persuade    |
| verifier of its validity.                                            |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Options: 
|       [C]laim the statement 
|       [D]etermine parameters and polynomial 
|       [Q]uit
d
| Please first send the number of variable and the degree of your desired polynomial:
5,3
| Now, please send the 5-variable polynomial as p: 
x0^3
| Options: 
|       [C]laim the statement 
|       [D]etermine parameters and polynomial 
|       [Q]uit
c
| Please send the g: 
1
| Please send the (p_0, h4sh(p_0, q)): 
| Note that the variable of p_0 should be x. 
x^3,1
| Please send the (p_1, h4sh(p_1, q)): 
| Note that the variable of p_1 should be x. 
x^3,1
| Please send the (p_2, h4sh(p_2, q)): 
| Note that the variable of p_2 should be x. 
x^3,1
| Please send the (p_3, h4sh(p_3, q)): 
| Note that the variable of p_3 should be x. 
x^3,1
| Please send the (p_4, h4sh(p_4, q)): 
| Note that the variable of p_4 should be x. 
x^3,1
| Congrats, here the flag: b'CCTF{Rem3Mb3er_tH4t_F14t_5h4m1r_tR4nsf0rm4tiOn_n33Ds_A_g00D_r4Nd0m_Or4cLe!}'

唔？这是 Tough？非预期啦？还是 Tough 在题目有点绕？

ASIv2

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def base(n, l):
    D = []
    while n > 0:
        n, r = divmod(n, l)
        D.append(r)
    return ''.join(str(d) for d in reversed(D)) or '0'

def asiv_prng(seed):
	l = len(seed)
	_seed = base(bytes_to_long(seed), 3)
	_l = len(_seed)
	R = [[getRandomRange(0, 3) for _ in range(_l)] for _ in range(_l**2)]
	S = []
	for r in R:
		s = 0
		for _ in range(_l):
			b = ((int(r[_]) + int(_seed[_])) % 3) % 2
			s = s ^ b
		S.append(s)
	print(len(S))
	return R, S

seed = flag.lstrip(b'CCTF{').rstrip(b'}')
R, S = asiv_prng(seed)

f = open('output.txt', 'w')
f.write(f'R = {R}\nS = {S}')
f.close()

ASIv1 的升级版，区别在于，

前者是 $S_1 \equiv \sum_{i=0}^n r_i \cdot s_i \pmod 3$，

现在是 $S_2\equiv \oplus _{i=0}^{n}(((r_i+s_i) \mod 3) \mod 2)$

我们知道，在$\mod 2$ 下，异或和相加是一样的，所以 $S_2$ 可以改为 $S_2\equiv \sum _{i=0}^{n}((r_i+s_i) \mod 3) \mod 2$，但这两次模该怎么处理呢？

我们列一个真值表

r	s	r+s	mod 3	mod 2	(mod 3) mod 2
0	0	0	0	0	0
0	1	1	1	1	1
0	2	2	2	0	0
1	0	1	1	1	1
1	1	2	2	0	0
1	2	3	0	1	0
2	0	2	2	0	0
2	1	3	0	1	0
2	2	4	1	0	1

因此如果 $r_i+s_i$ 的分布相对均匀的话，那么 $b$ 为 $1$ 的概率应该是 $1/3$，$b$ 为 $0$ 的概率应该是 $2/3$。（然并卵）我们需要的是找到一个线性表达式来表示 $seed,R,S$，即我们需要找到一个线性映射，满足

r	s	o
0	0	0
0	1	1
0	2	0
1	0	1
1	1	0
1	2	0
2	0	0
2	1	0
2	2	1

我们考虑用向量来表示 $r,s$，例如，$f_r(0) \to (1,0,0)$，$f_s(0) \to (1,0,0)$，这样 $f_r(0) \cdot f_s(0) = 1$，不行不行，调整一下，$f_s(0)=(0,1,0)$，这样就能有 $f_r(0)\cdot f_s(0)=1$。以此类推，我们有
$$
f_r(0) \to (1,0,0),f_r(1) \to (0,1,0),f_r(2) \to (0,0,1)
$$

$$
f_s(0) \to (0,1,0),f_s(1) \to (1,0,0),f_s(2) \to (0,0,1)
$$

这样我们就有 $((r_i+s_i) \mod 3) \mod 2 \equiv f_r(r) \cdot f_s(s) \pmod 2$，就是线性的了！

于是我们有 $S_2 \equiv \sum_{i=0}^n f_r(r)\cdot f_s(s) \pmod 2$

from Crypto.Util.number import *

def f_r(r):
	fr = []
	mapping_r = {0:[1,0,0],1:[0,1,0],2:[0,0,1]}
	for each in r:
		t = []
		for i in each:
			t+=mapping_r[i]
		fr.append(t)
	return fr

with open("output.txt") as f:
	data = f.read().split("\n")

R = eval(data[0][4:])
S = eval(data[1][4:])
FR = f_r(R)
RR = matrix(Zmod(2),FR[:375])
SS = vector(Zmod(2),S[:375])
mm = RR.solve_right(SS)

for i in range(0,len(mm),3):
    print(mm[i:i+3])
	print(mapping_s_inv[tuple(mm[i:i+3])])

(0, 0, 1)
(0, 1, 0)
(1, 1, 0)
(1, 0, 0)
(0, 1, 0)
...

在我们解密后打算将明文向量逆映射回去，此时发现会有向量 $(1,1,0)$ 出现，这在我们的映射关系中是非法的（找不到原象），但是对于向量内积来说是合理的。因此我们需要额外考虑一下这个向量还可以由哪个值映射过来。这里暴力一点就是直接莽，en试，于是

mapping_s_inv = {(1,0,0):"1",(0,1,0):"0",(0,0,1):"2",(1,1,0):"2"}

flag = ""
for i in range(0,len(mm),3):
	flag += (mapping_s_inv[tuple(mm[i:i+3])])

flag = int(flag,3)
print(long_to_bytes(flag))

b'4n0Th3R_47tACkER_!n_Vi5A!'

（PS：测完发现，$(1,1,0)$ 和 $(0,0,1)$ 是各位取反，因此可以大胆猜测一下，$(0,0,1) \to 1,(1,1,0) \to 0$）

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com